Past exam question: 2074 Bhadra (Regular), Q6
Open in the Padhaiko appQuestion
What is tree recursion? Write an algorithm for TOH with 'n' disks and generate a recursion tree of TOH problem with 3 disks.
Solution
Tree Recursion: Tree recursion occurs when a recursive function invokes itself more than once within a single execution of its body, forming a branching tree of activation calls (e.g., fibonacci(n) or TOH(n)).
Tower of Hanoi Algorithm (n Disks):
Algorithm TOH(n, src, aux, dst):
1. If n == 1:
Print "Move disk 1 from", src, "to", dst
Return
2. TOH(n - 1, src, dst, aux)
3. Print "Move disk", n, "from", src, "to", dst
4. TOH(n - 1, aux, src, dst)Recursion Tree for TOH(3, A, B, C):
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]
Moves in order: A->C, A->B, C->B, A->C, B->A, B->C, A->C ( moves).
Answer:
Tree recursion makes two or more recursive calls per invocation. For 3 disks, TOH(3, A, B, C) produces a binary recursion tree of 7 leaf/internal disk moves (2^3 - 1 = 7).