PadhaikoAll subjects

Past exam question: 2078 Poush (Back), Q3(a)

Data Structure and Algorithms · 6 marks

Open in the Padhaiko app

Topic: Recursion

Question

Explain different types of recursion. Construct a recursion tree for Tower of Hanoi with 3 disks.

Solution

Types of Recursion:

  1. Direct Recursion: A function calls itself directly inside its own body.
    • Linear / Tail Recursion: At most one recursive call per invocation; in tail recursion, the recursive call is the very last action before returning (e.g., gcd(a, b)).
    • Non-Tail / Head Recursion: Further computation remains after the recursive call returns (e.g., n * fact(n - 1)).
    • Tree Recursion: A function makes two or more recursive calls in one invocation (e.g., fibonacci, TOH).
  2. Indirect (Mutual) Recursion: Function A() calls B(), which calls A() back.
  3. Nested Recursion: The argument passed to a recursive call is itself another recursive call (e.g., Ackermann's function).

Recursion Tree for TOH(3, A, B, C) (Source A, Auxiliary B, Destination C): Each call TOH(n, src, aux, dst) expands into TOH(n-1, src, dst, aux) move disk TOH(n-1, aux, src, dst):

                        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 disk moves = : A->C, A->B, C->B, A->C, B->A, B->C, A->C.

Answer:

Recursion types include direct (tail, non-tail/head, linear, tree), indirect, and nested recursion. For 3 disks, the Tower of Hanoi recursion tree has 3 levels of TOH calls producing disk moves: A->C, A->B, C->B, A->C, B->A, B->C, A->C.

All past exam questions for Data Structure and Algorithms