Tower of Hanoi has a wonderful history. However, we are going to talk about the recursive solution of the Tower of Hanoi here. It’s a perfect problem to train your brain. It will help you in excelling at programming. Here, you will get the recursive solution of Tower of Hanoi in C.

#### What is Tower of Hanoi?

Tower of Hanoi is a mathematical game or puzzle. It is also known as Lucas tower or tower of Brahma. It was invented in 1833 by a French mathematician named Edouard Lucas. The puzzle contains three rods and disks of different sizes. The disks are slid onto the rod. This tower of Hanoi came into existence because of an Indian temple at Kashi Vishwanath.

The disks are always stacked in ascending order on one rod. The smallest disk is kept at the top. It can be played with the help of numerous disks. The least number of required moves for solving the Tower of Hanoi puzzle is 2^{n} – 1, where n refers to the number of disks. It can’t be solved without following few rules that are as follows:

- At a time, only one disk is allowed to move
- In every move, the topmost disk can be removed from a stack. It can be placed on another rod
- You can’t place any larger disk on a small one

If we will use three disks, then the problem will get solved in seven moves. It seems simple but it’s not. You have to know the concept of recursion and algorithm. The problem will be broken down into smaller problem so that it will become easy to solve recursively.

1. /*
2. * C program for Tower of Hanoi using Recursion
3. */
4. #include
5.
6. void towers(int, char, char, char);
7.
8. int main()
9. {
10. int num;
11.
12. printf("Input the number of disks : ");
13. scanf("%d", &num);
14. printf("The sequence of moves for solving the Tower of Hanoi are :\n");
15. towers(num, 'A', 'C', 'B');
16. return 0;
17. }
18. void towers(int num, char frompeg, char topeg, char auxpeg)
19. {
20. if (num == 1)
21. {
22. printf("\n Move disk 1 from peg %c to peg %c", frompeg, topeg);
23. return;
24. }
25. towers(num - 1, frompeg, auxpeg, topeg);
26. printf("\n Move disk %d from peg %c to peg %c", num, frompeg, topeg);
27. towers(num - 1, auxpeg, topeg, frompeg);
28. }
#### Output

Input the number of disks : 3
The sequence of moves for solving the Tower of Hanoi are :
Move disk 1 from peg A to peg C
Move disk 2 from peg A to peg B
Move disk 1 from peg C to peg B
Move disk 3 from peg A to peg C
Move disk 1 from peg B to peg A
Move disk 2 from peg B to peg C
Move disk 1 from peg A to peg C
You can understand the working of code with the help of the given output. I hope you have understood about the Tower of Hanoi and how it can be solved recursively in C.

Our Quiz prepared by Experts Helps you identify your knowledge in Algorithms. Everyone should atleast attempt this Quiz Once.