PadhaikoAll subjects

Past exam question: 2062 Baishakh (Regular / Back), Q3

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Recursion

Question

Discuss the efficiency of recursion. Draw the recursion tree for tower of Hanoi problem for 5 disks. Show execution path according to TOH algorithm.

Solution

Efficiency of Recursion:

Recursion Tree for TOH(5, A, B, C) ( Moves): T(n) denotes TOH(n, src, aux, dst); each internal node executes Left subtree Move disk Right subtree:

                                     T(5,A,B,C)
                        /                 |                 \
               T(4,A,C,B)              [5: A->C]           T(4,B,A,C)
              /     |     \                               /     |     \
        T(3,A,B,C) 4:A->B T(3,C,A,B)                T(3,B,C,A) 4:B->C T(3,A,B,C)
        /   |   \          /   |   \                 /   |   \          /   |   \
    T(2) 3:A->C T(2)   T(2) 3:C->B T(2)          T(2) 3:B->A T(2)   T(2) 3:A->C T(2)
   / | \       / | \  / | \       / | \         / | \       / | \  / | \       / | \
  1  2  1     1  2  1 1  2  1    1  2  1       1  2  1     1  2  1 1  2  1    1  2  1

(Each T(2) expands into [disk 1] -> [disk 2] -> [disk 1], giving 16 leaf moves for disk 1, 8 moves for disk 2, 4 moves for disk 3, 2 moves for disk 4, and 1 move for disk 5.)

Complete 31-Move Execution Path (TOH(5, A, B, C)): 1–7 (first T(3) A->C): A->C, A->B, C->B, A->C, B->A, B->C, A->C 8: A->B (disk 4) 9–15 (T(3) C->B): C->B, C->A, B->A, C->B, A->C, A->B, C->B 16: A->C (disk 5) 17–23 (T(3) B->A): B->A, B->C, A->C, B->A, C->B, C->A, B->A 24: B->C (disk 4) 25–31 (T(3) A->C): A->C, A->B, C->B, A->C, B->A, B->C, A->C

Answer:

Recursion incurs stack space and call overhead ( time for TOH). For 5 disks, the TOH(5, A, B, C) recursion tree has 5 levels and executes moves in exact depth-first in-order sequence.

All past exam questions for Data Structure and Algorithms