Past exam question: 2078 Poush (Back), Q3(a)
Open in the Padhaiko appQuestion
Explain different types of recursion. Construct a recursion tree for Tower of Hanoi with 3 disks.
Solution
Types of Recursion:
- Direct Recursion: A function calls itself directly inside its own body.
- Linear / Tail Recursion: At most one recursive call per invocation; in tail recursion, the recursive call is the very last action before returning (e.g.,
gcd(a, b)). - Non-Tail / Head Recursion: Further computation remains after the recursive call returns (e.g.,
n * fact(n - 1)). - Tree Recursion: A function makes two or more recursive calls in one invocation (e.g.,
fibonacci,TOH).
- Linear / Tail Recursion: At most one recursive call per invocation; in tail recursion, the recursive call is the very last action before returning (e.g.,
- Indirect (Mutual) Recursion: Function
A()callsB(), which callsA()back. - Nested Recursion: The argument passed to a recursive call is itself another recursive call (e.g., Ackermann's function).
Recursion Tree for TOH(3, A, B, C) (Source A, Auxiliary B, Destination C): Each call TOH(n, src, aux, dst) expands into TOH(n-1, src, dst, aux) move disk TOH(n-1, aux, src, dst):
TOH(3, A, B, C)
/ | \
TOH(2, A, C, B) [A -> C] TOH(2, B, A, C)
/ | \ / | \
TOH(1,A,B,C) [A->B] TOH(1,C,A,B) TOH(1,B,C,A) [B->C] TOH(1,A,B,C)
[A->C] [C->B] [B->A] [A->C]
Total disk moves = : A->C, A->B, C->B, A->C, B->A, B->C, A->C.
Answer:
Recursion types include direct (tail, non-tail/head, linear, tree), indirect, and nested recursion. For 3 disks, the Tower of Hanoi recursion tree has 3 levels of TOH calls producing disk moves: A->C, A->B, C->B, A->C, B->A, B->C, A->C.