Tower of Hanoi in C

The Tower of Hanoi puzzle is a classic example that illustrates the principle of recursion, especially when implemented in the C programming language. It combines mathematics, logic, and programming concepts. It helps build a clear understanding of recursion

In this blog, we will study what the Tower of Hanoi problem is, and we will implement the solution in the C programming language. We will also analyze the mathematical logic and complexity behind the Tower of Hanoi and real-world applications.

Table of Contents:

• What is the Tower of Hanoi?
• What is the Problem of the Tower of Hanoi?
• Why is the Tower of Hanoi important in computer science and recursion?
• Historical Background and the Tower of Hanoi
• What is the Solution to the Tower of Hanoi in C?
  • Solution of the Tower of Hanoi using Recursion
  • Solution of the Tower of Hanoi using the Iterative Method
• Mathematical Analysis: Minimum Number of Moves
• Real-Life Applications of the Tower of Hanoi
• Conclusion

What is the Tower of Hanoi?

The Tower of Hanoi is a classical mathematical puzzle that involves moving the stack of discs from one rod (tower) to another, following a specific pattern. The goal is to move the whole stack of discs from one rod to the other. This process continues recursively until the stack of discs is transferred from one rod to the other. There are three towers: the origin tower, where the discs are kept; the auxiliary tower, which is used as a temporary storage space for the discs; and the destination tower, which is the final tower where the discs are moved to.

What is the Problem of the Tower of Hanoi?

Let’s understand the Tower of Hanoi problem with a diagram:

Here in the above image, we have three towers. One of them is loaded with an n number of discs of different sizes, in descending order (largest-diameter disc at the bottom and smallest-diameter disc at the top). The motive of this problem is to move all the discs from the origin tower to the destination tower by using a third tower, without changing the order of the discs. Only one disc can be moved at a time, as per the rules

The above image is wrong, even though all the discs are moved to the destination tower, because the sequence of the discs is wrong.

This is the correct way of the Tower of Hanoi.

Why is the Tower of Hanoi important in computer science and recursion?

The Tower of Hanoi plays an important role in the field of computer science as it is a clear and elegant example of recursion, which is a powerful problem-solving technique where a function calls itself on the smaller instances of the same problem. It is a good illustration of the “divide and conquer algorithm,” in which complex problems are broken down into smaller subproblems.

Reasons Why the Tower of Hanoi is Important

Given below are the reasons why the Tower of Hanoi is important:

• Divide and Conquer – It demonstrates the divide and conquer algorithm by dividing the problem of moving n number of discs into smaller problems of moving n-1 discs. This approach is more efficient than solving the entire problem at once for a large number of discs.
• Recursion – The Tower of Hanoi is a good example of recursion. To move a stack of n number of discs, we recursively move n-1 number of discs from the origin tower to an intermediate tower, then move the largest disc directly to the destination tower. Ultimately, we will move the n-1 number of discs from the intermediate tower to the destination tower. The same process is done until all the discs are moved to the destination tower in a particular order (from the largest disc at the bottom to smallest disc at the top).
• Algorithm Analysis – The Tower of Hanoi illustrates how algorithm complexity grows exponentially, as it has an exponential time complexity of O(2^n) and space complexity of O(n).

Historical Background and the Tower of Hanoi

The Tower of Hanoi was invented by French mathematician Édouard Lucas in the year 1883. According to legend, in a Hindu temple in Kashi Vishwanath, India, priests were asked to move 64 golden discs between three poles, following specific rules. Although the priests suggested that it was of ancient origin, the puzzle itself is relatively modern and was invented by Lucas. Lucas may have drawn inspiration from a similar game that he came across in Vietnam, a French colony at that time, and renamed it the Tower of Hanoi. It involves moving n number of discs of different sizes from one pole to the other with a rule that the largest disc will come at the bottom and the smallest will come at the top. In computer science, it is used to illustrate recursion and data structures.

What is the Solution to the Tower of Hanoi in C?

The Tower of Hanoi can be solved mainly by using recursion. Its main objective is to move all the discs from the initial tower to the destination tower without changing the order of the discs; that is, the largest diameter disc will be at the bottom, and the smallest diameter disc will come at the top. A larger disc cannot be placed on top of a smaller one. It obeys the rule that only one disc can be moved at a time.

1. Solution of the Tower of Hanoi using Recursion

Let’s see the Tower of Hanoi problem in C programming using recursion. Recursion is a function that calls itself to solve a smaller part of the program. Given below is the code for a recursion example in C for the Tower of Hanoi.

Output

In this recursive implementation, the function calls itself to move n-1 disks before and after moving the nth disk.

2. Solution of the Tower of Hanoi using the Iterative Method

Let’s see the C programming using iteration to solve the Tower of Hanoi. Iteration is the process of repeating a set of instructions until a given condition is met. As we are using iteration instead of recursion, bitwise logic will be used. It helps in moving the discs from the source tower to the destination tower by following certain rules.

Output

In this iterative implementation, disc movements are simulated step-by-step using a loop and bitwise logic without using recursion.

Mathematical Analysis: Minimum Number of Moves

In the Tower of Hanoi, the minimal number of moves required to solve the problem for n discs is given by the formula

Minimum Moves = 2ⁿ − 1,

where n is the number of discs.

Time Complexity

With the number of discs, the number of recursive calls grows exponentially, and each of the recursive calls spawns two nested calls until the base case is reached. The time complexity of the Tower of Hanoi is O(2^n).

Space Complexity

As each level calls the next level once, the maximum depth of the recursion stack is n. The space complexity of the Tower of Hanoi is O(n).

Real-Life Applications of the Tower of Hanoi

Some of the real-world applications of the Tower of Hanoi:

1. Recursion and Algorithm – The Tower of Hanoi problem is a classical illustration for teaching recursion; it follows the divide and conquer algorithm, as it divides the large problem into smaller subproblems.
2. Problem-Solving Research – To understand human problem-solving abilities, it can be used in psychological studies.
3. Logistics and Resource Management – The efficient movement of the discs from one tower to the other can be similar to optimizing logistics and resource allocation in various real-world scenarios.
4. Mathematical Exploration – In mathematics, the Tower of Hanoi is used to study the concept of recursion, as it illustrates a good example of recursion.
5. Data Structures – It serves as a good example of stack operations, push and pop, and also shows how the data can be manipulated in a structured way.

C Programming and DSA Free Course

Learn C for Free – Start Coding!

Explore Program

Conclusion

In this blog, we have explored the Tower of Hanoi problem, understood its recursive and iterative solutions in C, and analyzed its time and space complexities. This puzzle not only clears our understanding of recursion but also makes our problem-solving skills strong, making it a must-learn concept for C programmers.

Tower of Hanoi in C – FAQs