Home

Learning Hub

Articles

C Program for Tower of Hanoi – A Deep Dive

The Tower of Hanoi is a well-known problem in the earlier version of the algorithm design, the object is to transfer a set of disks from one rod to another. Nevertheless, it is not that simple, as only one disk may be moved at once, and no disk may be put on top of a smaller one. The challenge is to transfer all the disks to the target rod while strictly respecting these constraints, using an auxiliary rod for storing temporarily.

We solve the Tower of Hanoi in this program using an iterative and recursive way. The recursive method solves the problem by breaking it into smaller sub-problems, n-1 disks are moved to the auxiliary rod and finally the large disk on the auxiliary rod. We also present an iterative version, which calculates moves using bitwise operations, serving as an alternative, non-recursive solution.

You’ll see how the disks are shifted from one rod to another in each step, and the output is rephrased in a user-friendly and intuitive way to let you know precisely what move has been made in each step. The solution utilizes the elegance of algorithm design when solving the problem and moving the disks optimally in terms of disk movement regardless of whether we are using recursion or iteration.

Also Read: Structure of C Program

Rules to Consider

Before we get into the solving of the Tower of Hanoi, let’s list down the basic rules:

• It is possible to move only one disk at a time.
• A stack can only be moved only one disk at a time with locking on only the top disk to work with.
• An empty rod can support a disk or an empty disk can sit on top of a larger one.

The first objective is to move the disks from the source rod to the destination rod, using an auxiliary rod at times. You just have to remember that each of the moves follows the rules, so when several disks get bigger it becomes a difficult problem.

Concept Behind the Tower of Hanoi

There’s a neat formula that gives you the minimum number of moves required:

So, that implies, if you follow the rules, you are going to have at least 7 transfers for all disks from one end rod to the other end rod. Then, you try solving the problem for higher values of N and you see that it is getting exponentially harder!

Types of Solutions for Tower of Hanoi

There are two different ways to approach the Tower of Hanoi:

• Recursion
• Iteration

Tower of Hanoi: Recursive Solution

Recursion is what makes the Tower of Hanoi such a secret sauce. So what is recursion? Or at least this is what I imagine it to be – where a function is solving itself to break down (or solve) a smaller (more manageable) problem of the same issue. This way one can solve the Tower of Hanoi, indeed, this.

Also Read: Important Features of C Language

Here’s the breakdown of the recursive solution:

• Shift top n – 1 disks from the source rod to the auxiliary rod.
• In the nth (largest) move the disk directly to the destination rod.
• Now place n – 1 disks on a temporary rod such that it is wirelessly linked to the destination rod(s).

Because we can break the solution for each step described above into this single little step, a smaller version of the original problem, recursion fits here so nicely.

Understanding the Recursion Tree

Seeing how recursion works in terms of this problem will help us understand intuitively. Think of it like a tree: The recursive call starts by moving the big problem (moving all the disks), then moves each of the remaining problems into simpler blocks of problems until you’re finally down to the simplest problem of moving just one disk.

For example, with 3 disks:

• Discs 1 and 2 indicate the auxiliary rod’s side.
• Disk 3 must then be moved to the destination rod.
• Transfer disk 1 first, then disk 2 to the destination rod.

But if you map it out you will see it is a tree in recursive calls and each move is broken down until you cannot break them down anymore.

Recursive Solution Using C

So now that we understand the logic we move on to the code.

Code:

Output:

This program defines the towerOfHanoi function, which takes four arguments: from_rod, to_rod, and aux_rod, the number of disks (n). Using recursion, the function then moves the disks according to the rules we arrive at.

Also Read: What is Recursion in C?

• Base Case: If there is one disk it is simply brought directly from source to destination. It’s the simplest possible scenario – and that’s as far down the recursion as it goes.
• Recursive Case: It does the whole trick, all at once for more than one disk by moving n-1 disks to the auxiliary rod; moving the nth (heaviest) disk to the destination rod and then moving the n-1 disks from the auxiliary rod to the destination.

It continues until all of the disks get put into their destination rod. Let’s run through an example with n = 3 disks to see how the program works:

• The program first moves disk 1 from rod A to rod C.
• Then, it moves disk 2 from rod A to rod B.
• Next, it moves disk 1 from rod C to rod B.
• Disk 3 is moved from rod A to rod C.
• Then, disk 1 is moved from rod B to rod A.
• Disk 2 is moved from rod B to rod C.
• Finally, disk 1 is moved from rod A to rod C.

Iterative Method for Tower of Hanoi

While recursion is elegant, it’s not always the only solution. The iterative method can also be used to solve the Tower of Hanoi problem. This approach typically uses loops and may involve stacks to manage the disk movements.

Below is a simple C program that implements the Tower of Hanoi using iteration:

Output:

In this program:

• The tower Of Hanoi Iterative is used to determine the total number of moves and how to move disks depending upon the number of disks used.
• In the case of an even number of disks, the logic of swapping rods is used.
• The position of the source and destination rod for creating the moves are calculated, and then it generates the moves.

Also Read: C Programming Interview Questions and Answers

Comparing Recursive and Iterative Methods

• Recursion: This method is often more straightforward to implement for problems like the Tower of Hanoi. However, it can consume more memory due to the function call stack.
• Iteration: The iterative method can be more efficient in terms of memory usage, but it may be harder to understand and implement for those who are new to algorithms.

Complexity Analysis

With the n disks known, the time complexity of the problem of a recursive Tower of Hanoi solution is O(2^n). The reason that is exponential time is because each disk incurs double the number of moves: It doubles in several moves for every additional disk.

Space complexity = depth of recursion stack = number of disks.

Applications of Tower of Hanoi

The Tower of Hanoi is more than just a puzzle because it has real-world applications, particularly in computer science:

• Algorithm Design: Using recursive solutions to solve the divide and conquer strategies in various algorithms, this problem demonstrates the utility of such.
• Data Structures: We can learn how stack operations work in programming by mapping the puzzle to stack operations.
• Disk Scheduling: The Tower of Hanoi is used in disk scheduling algorithms in the Operating systems.

Common Mistakes

It’s easy to make mistakes while implementing the Tower of Hanoi problem, and it’s easy to implement too. Some common issues include:

• Being trapped inside infinite recursion will be a result of forgetting the base case.
• Incorrect outputs may occur when the order of recursive calls is misplaced.

I think most problems are solvable by printing or stepping through the code.

Conclusion

The Tower of Hanoi is a great puzzle to get us thinking and that helps us practice recursion and iteration. This article has taught us how to solve things in C, demonstrating the beautiful beauty of recursive methods and the efficiency of iterative otherwise. Solving this problem not only makes you a sharper programmer, it gives you great insight into algorithm design and problem-solving techniques. The Tower of Hanoi is an old challenge that doesn’t matter whether you are a beginner or a seasoned programmer: it improves your understanding of complex algorithms. If you’re planning to kickstart your tech career, consider pursuing Hero Vired’s Certificate Program in DevOps & Cloud Engineering offered in collaboration with Microsoft.