PadhaikoAll subjects

Past exam question: 2078 Baishakh (Back), Q4

Data Structure and Algorithms · 6 marks

Open in the Padhaiko app

Topic: Recursion

Question

What is recursion? Write recursive module for Tower of Hanoi (ToH) problem.

Solution

Definition of Recursion: Recursion is a programming technique in which a function calls itself (directly or indirectly) to solve smaller subproblems of the same type until reaching one or more base cases that terminate without further self-calls.

Recursive Module for Tower of Hanoi (ToH): To move n disks from source (A) to destination (C) using auxiliary (B):

  1. If n == 1, move disk 1 directly from source to destination.
  2. Otherwise:
    • Recursively move n - 1 disks from source to auxiliary using destination.
    • Move the -th disk from source to destination.
    • Recursively move n - 1 disks from auxiliary to destination using source.
void toh(int n, char src, char aux, char dst) {
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", src, dst);
        return;
    }
    toh(n - 1, src, dst, aux);
    printf("Move disk %d from %c to %c\n", n, src, dst);
    toh(n - 1, aux, src, dst);
}
Total moves for `n` disks = , time complexity , auxiliary stack space .
Answer:

Recursion solves a problem by reducing it to smaller self-calls down to a terminating base case. The toh(n, src, aux, dst) module recursively moves n - 1 disks to aux, moves disk n to dst, and moves n - 1 disks from aux to dst in moves.

All past exam questions for Data Structure and Algorithms