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:

- Only one disk may be moved at a time.
- 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.
- 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 `2`

where ^{n} − 1,`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 ^{n})**

Here’s a working example: Tower of Hanoi

**Reference:** Pepcoding

## One thought on “Tower of Hanoi | Recursion using Mathematical Induction”