PadhaikoAll subjects

Past exam question: 2076 Baisakh (Back), Q6

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Recursion

Question

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:

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.

All past exam questions for Data Structure and Algorithms