Past exam question: 2078 Baishakh (Back), Q4
Open in the Padhaiko appQuestion
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):
- If
n == 1, move disk 1 directly fromsourcetodestination. - Otherwise:
- Recursively move
n - 1disks fromsourcetoauxiliaryusingdestination. - Move the -th disk from
sourcetodestination. - Recursively move
n - 1disks fromauxiliarytodestinationusingsource.
- Recursively move
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.