## What is the Tower of Hanoi?

Tower of Hanoi is a game where a certain number of disks of different sizes residing on a particular rod needs to be transferred into the final rod with the help of other available rods. But there is some condition:

- One Disk at a time is allowed for shifting.
- Large Disk cannot be put over smaller disk.

Initially, we have this situation:

What we want is this by following the above rules:

## Tower of Hanoi in C using Recursion

To solve **the Tower of Hanoi using C program** using Recursion, we need to understand a little trick and the concept of Recursion. The trick lies in the algorithm.

### Algorithm – The Trick

Suppose we are given 3 (n) disk as stated in the first diagram and asked to solve this using recursion. And we also know that putting large disk over small one is not allowed.

The trick is to **assume that we are given only two disks** (as stated in the picture).

Now we need to shift the upper disk i.e n-1 (which actually contains 2 Disk in the current scenario) to B so that we can shift the last disk (n-th) to C.

The main point is we will not do this. The recursive function will take the responsibility to shift n-1 disks (2 disks in this case) to B.

1 |
hanoi(n-1,rodFrom,rodTo,rodMiddle); |

where * rodFrom = A* ,

**and**

*rodTo = B**will be used as auxiliary rod by the recursive function.*

**rodMiddle = C**Now we need to shift last disk (nth or largest disk) to rod C. So we will do this Just by outputting the statement.

1 |
printf("Disk %d moved from %c to %c \n",n,rodFrom,rodTo); |

where ** n=3**,

*and*

**rodFrom = A**

*rodTo = C**.*

Now again the n-1 disk (2 disks) in rod B need to be shifted to C with the help of rod A. Since there are multiple disk i.e n-1, so let the recursive function handle this task. So we will write

1 |
hanoi(n-1,rodMiddle,rodFrom,rodTo); |

where * rodFrom = B* ,

**and**

*rodTo = C**will be used as auxiliary rod by the recursive function.*

**rodMiddle = A**Finally, we will get this i.e Tower of Hanoi solved.

## Tower of Hanoi C Program

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include <stdio.h> #include <stdlib.h> int main() { hanoi(3, 'A', 'B', 'C'); return 0; } void hanoi(int n, char rodFrom, char rodMiddle, char rodTo){ if(n==1){ printf("Disk 1 moved from %c to %c \n",rodFrom,rodTo); return; } hanoi(n-1,rodFrom,rodTo,rodMiddle); printf("Disk %d moved from %c to %c \n",n,rodFrom,rodTo); hanoi(n-1,rodMiddle,rodFrom,rodTo); } |

**Output**

We have shown you 3 disk Tower of Hanoi problem. This C program can be used to solve any number of Disk in Tower of Hanoi game i.e any value of n. If you have doubt then comment below.