Tower of Hanoi | Recursion using Mathematical Induction

The Tower of Hanoi is a mathematical puzzle (game) consisting of three rods and a number of disks of varying diameters, which can slide onto all the three rods. The puzzle begins with the disks stacked on first rod (A) in order of increasing size from the top, with smallest at the top.

The objective of the puzzle is to move all the disks from the first rod (A) to the next rod (B) using the auxiliary rod (C), obeying the following rules:

1. Only one disk may be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
3. No disk may be placed on top of a disk that is smaller than it.

The minimal number of moves required to solve a Tower of Hanoi puzzle is 2n − 1, where n is the number of disks. Given n number of disks, you need to print all the steps to move all the disks from the rod A to rod B, where a step is written as, A->B, which denotes: move the top most disk from the rod A to the top of rod B.

Mathematical Induction

Mathematical induction is a mathematical proof technique. It is used to prove that a statement P(n) holds for every natural number n = 0, 1, 2, 3, …
A proof by induction has two cases:

• The first case, the base case, is to solve the statement for n = 1.
• The second case, the induction step, is to solve the statement for the next case n = k + 1, given that the statement holds for any given n = k.

These two steps is enough to prove that the statement holds for every natural number n.

Recursive Approach

Hypothesis

towerOfHanoi (n, A, B, C) will print all the steps to move n disks from A to B using C.

Base Case

Only one disk i.e. n = 1

Pseudocode

printf("%c -> %c", A, B); //base case: move A to B

Expectation

towerOfHanoi (n-1, A, B, C) will print all the steps to move n-1 disks from A to B using C.

Induction

We need to prove the hypothesis that towerOfHanoi (n, A, B, C) will print all the steps to move n disks from A to B using C, with the help of towerOfHanoi (n-1, A, B, C).

Pseudocode

towerOfHanoi (n-1, A, C, B) //move n-1 disks from A to C using B
printf("%c -> %c", A, B) //base case: move disk from A to B
towerOfHanoi (n-1, C, B, A) //move n-1 disks from C to B using A

Code Implementation

//
//  main.cpp
//  Tower of Hanoi
//
//  Created by Himanshu on 05/04/22.
//

#include <iostream>

void towerOfHanoi (int n, char from, char to, char aux) {
    if (n <= 0) {
        return;
    }
    
    towerOfHanoi(n-1, from, aux, to);
    printf("%c -> %c\n", from, to);
    towerOfHanoi(n-1, aux, to, from);
}

int main () {
    int n = 3;

    towerOfHanoi(n, 'A', 'B', 'C');

    return 0;
}

Output

A -> B
A -> C
B -> C
A -> B
C -> A
C -> B
A -> B

Time complexity: O(2ⁿ)

Here’s a working example: Tower of Hanoi

Reference: Pepcoding