PadhaikoAll subjects

Past exam question: 2074 Bhadra (Regular), Q6

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Recursion

Question

What is tree recursion? Write an algorithm for TOH with 'n' disks and generate a recursion tree of TOH problem with 3 disks.

Solution

Tree Recursion: Tree recursion occurs when a recursive function invokes itself more than once within a single execution of its body, forming a branching tree of activation calls (e.g., fibonacci(n) or TOH(n)).

Tower of Hanoi Algorithm (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]

Moves in order: A->C, A->B, C->B, A->C, B->A, B->C, A->C ( moves).

Answer:

Tree recursion makes two or more recursive calls per invocation. For 3 disks, TOH(3, A, B, C) produces a binary recursion tree of 7 leaf/internal disk moves (2^3 - 1 = 7).

All past exam questions for Data Structure and Algorithms