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 this classic puzzle and its 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 Problem?
  • Recursive Solution in C
  • Iterative Approach in C
• Mathematical Analysis: Minimum Number of Moves
• Code Optimization Techniques in Tower of Hanoi
• Real-Life Applications of the Tower of Hanoi
• Common Mistakes and Pitfalls in Tower of Hanoi
• Debugging Tips in 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 this 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 to solve this problem.

Why is the Tower of Hanoi Important in Computer Science and Recursion?

This classical mathematical puzzle 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 this problem 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 – It is a good example of recursion. To move a stack with”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 the smallest disc at the top).
• Algorithm Analysis – This classic puzzle 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

This problem 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 Problem?

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. Recursive Solution in C

Let’s see this 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 Recursive C program 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. Iterative Approach in C

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

The minimal number of moves required to solve this 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).

Code Optimization Techniques in Tower of Hanoi

• Avoid Unnecessary Calculations or Prints: Always be careful to avoid repeating the same calculations or having too many debug print statements in the final version. Remove all unnecessary output, and only keep the useful output.
• Apply Tail Recursion (if supported): Tail recursion can be done in some languages through compiler optimizations that reduce memory usage. In C, this requires care in structuring your program, but it is useful to know about.
• Memoization for Variations: If you consider solving variants of the Tower of Hanoi when the same state is repeated, you can use memoization to avoid repeating the work.
• Limit Global Variables: Try to keep your function pure (no global state) so that it can be reused and will behave consistently and predictably for any input.
• Pre-calculate Total Moves: You can calculate the total number of moves using the formula (2^n – 1), which will allow you to track the progress of the solution or validate the output before completing it.

Real-Life Applications of the Tower of Hanoi

Some of the real-world applications of this problem are:

1. Recursion and Algorithm – The 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, it 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.

Common Mistakes and Pitfalls in Tower of Hanoi

1. Forgetting the Base Case: If you forget to use the base case, then recursion does not stop when only one disk is left, and thus your program can crash or run forever.
2. Mixing Up Rods: Confusing the source, destination, and helper rods gives the wrong steps and messes up the solution.
3. No Clear Disk Moves: If you do not clearly show which disk is moving from which rod to where, it’s hard to understand the output.
4. Trying to Manually Code All Moves: Manually solving for 2 or 3 disks might work, but it won’t scale. Use recursion so it works for any number of disks.
5. Wrong Disk Number or Input: Giving 0 or a negative number of disks will break the logic. Always check that the number of disks is at least 1.
6. Not Testing with Small Numbers First: Jumping into big numbers like 5 or 10 disks can be confusing. Start small to check if your code works correctly.

Debugging Tips in Tower of Hanoi

• Include Print Statements: Add print statements that display all of the parameters of each recursive call; this signals the flow of the algorithm.
• Test with Small Disk Numbers: Begin with n being equal to 1, 2, or 3 to validate correctness, before testing with larger n values.
• Draw the Tower Manually: For smaller input values, you could make the moves and follow along, comparing with your program’s output.
• Check for Stack Overflow: If you are working with a large n, be sure that your system’s recursion limit will not be reached and cause a stack overflow.
• Use Meaningful Names: Use meaningful names in your code, such as source, destination, and auxiliary, to help prevent confusion.

C Programming and DSA Free Course

Learn C for Free – Start Coding!

Explore Program

Conclusion

The Tower of Hanoi is a classic algorithm that strengthens your understanding of recursion, logic, and problem-solving in C programming. By learning both recursive and iterative solutions, you build a strong foundation in algorithms with real-world relevance. Its applications in AI, data structures, and computer science education make it a must-learn concept for everyone. 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