Past exam question: 2066 Jestha (Back), Q4
Open in the Padhaiko appQuestion
What are the types of recursion? Write an algorithm for Tower of Hanoi (TOH) and illustrate an algorithm for 3 disks.
Solution
Types of Recursion:
- Direct Recursion: Function invokes itself directly (tail, non-tail/head, linear, and tree recursion).
- Indirect (Mutual) Recursion: Function
AcallsB, which callsA. - Nested Recursion: Recursive call's argument is itself a recursive call.
Algorithm for Tower of Hanoi (TOH):
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)Illustration for 3 Disks (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]
7 moves in exact sequence: A->C, A->B, C->B, A->C, B->A, B->C, A->C.
Answer:
Recursion is classified into direct (tail, non-tail, linear, tree), indirect, and nested recursion. For 3 disks, TOH(3, A, B, C) performs moves: A->C, A->B, C->B, A->C, B->A, B->C, A->C.