Past exam question: 2062 Baishakh (Regular / Back), Q3
Open in the Padhaiko appDiscuss the efficiency of recursion. Draw the recursion tree for tower of Hanoi problem for 5 disks. Show execution path according to TOH algorithm.
Solution
Efficiency of Recursion:
- Time Overhead: Each recursive call pushes and pops an activation record on the call stack, making simple linear recursions slower per iteration than loops. Moreover, naive branching recursion (like
fib(n)) can take exponential time from overlapping subproblems, while Tower of Hanoi inherently requires moves (). - Space Overhead: Call-stack memory grows proportionally to maximum recursion depth ( for TOH), risking stack overflow for very deep calls.
Recursion Tree for TOH(5, A, B, C) ( Moves): T(n) denotes TOH(n, src, aux, dst); each internal node executes Left subtree Move disk Right subtree:
T(5,A,B,C)
/ | \
T(4,A,C,B) [5: A->C] T(4,B,A,C)
/ | \ / | \
T(3,A,B,C) 4:A->B T(3,C,A,B) T(3,B,C,A) 4:B->C T(3,A,B,C)
/ | \ / | \ / | \ / | \
T(2) 3:A->C T(2) T(2) 3:C->B T(2) T(2) 3:B->A T(2) T(2) 3:A->C T(2)
/ | \ / | \ / | \ / | \ / | \ / | \ / | \ / | \
1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1
(Each T(2) expands into [disk 1] -> [disk 2] -> [disk 1], giving 16 leaf moves for disk 1, 8 moves for disk 2, 4 moves for disk 3, 2 moves for disk 4, and 1 move for disk 5.)
Complete 31-Move Execution Path (TOH(5, A, B, C)): 1–7 (first T(3) A->C): A->C, A->B, C->B, A->C, B->A, B->C, A->C 8: A->B (disk 4) 9–15 (T(3) C->B): C->B, C->A, B->A, C->B, A->C, A->B, C->B 16: A->C (disk 5) 17–23 (T(3) B->A): B->A, B->C, A->C, B->A, C->B, C->A, B->A 24: B->C (disk 4) 25–31 (T(3) A->C): A->C, A->B, C->B, A->C, B->A, B->C, A->C
Recursion incurs stack space and call overhead ( time for TOH). For 5 disks, the TOH(5, A, B, C) recursion tree has 5 levels and executes moves in exact depth-first in-order sequence.