PadhaikoAll subjects

Past exam question: 2066 Jestha (Back), Q4

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Recursion

Question

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:

  1. Direct Recursion: Function invokes itself directly (tail, non-tail/head, linear, and tree recursion).
  2. Indirect (Mutual) Recursion: Function A calls B, which calls A.
  3. 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.

All past exam questions for Data Structure and Algorithms