Past exam question: 2076 Baisakh (Back), Q6
Open in the Padhaiko appQuestion
What are tail and non-tail recursions? Write an algorithm for TOH with 'n' disks and generate a recursion tree of TOH problem with 3 disks.
Solution
Tail vs. Non-Tail Recursion:
- Tail Recursion: The recursive call is the exact last operation executed in the function; no computation remains after the call returns, so compilers can optimize it into a loop (tail-call optimization).
- Example:
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
- Example:
- Non-Tail Recursion: Pending operations (multiplication, addition, or second recursive calls) wait for the recursive call's return value before finishing, requiring stack frames to remain active.
- Example:
int fact(int n) { return n <= 1 ? 1 : n * fact(n - 1); }
- Example:
Algorithm for Tower of Hanoi (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]
Total moves = : A->C, A->B, C->B, A->C, B->A, B->C, A->C.
Answer:
Tail recursion performs the recursive call as its final action, whereas non-tail recursion performs additional work after the call returns. The TOH(3, A, B, C) recursion tree generates moves.