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 placed 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 to temporarily store them.

We solve the Tower of Hanoi program in C 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 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 each step shifts the disks from one rod to another. The output is rephrased to be user-friendly and intuitive, letting you know precisely what move has been made in each step. The solution utilises the elegance of algorithm design to solve the problem and move the disks optimally, regardless of whether we use recursion or iteration.

Basic 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 one disk at a time, locking on only the top disk.
• 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 to the destination rod, sometimes using an auxiliary rod. Each move must follow the rules, so when several disks get bigger, the problem becomes difficult.

Also Read: C Programming Tutorial for Beginners

What is the formula for the Tower of Hanoi? There’s a neat formula that gives you the minimum number of moves required:

Moves = 2^n – 1

For n disks.

For example, if you have three disks, the minimum number of moves will be:

Moves = 2^3 – 1 = 7

So, if you follow the rules, you will have at least seven transfers for all disks from one end rod to the other. Then, when you try solving the problem for higher values of N, 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 algorithm 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.

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 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.

Also Read: C Programming Interview Questions and Answers

Understanding the Recursion Tree

Seeing how recursion works regarding 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 three 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 can no longer break them down.

Recursive Solution Using C

So, now that we understand the logic, we move on to the C program for tower of Hanoi using recursion. Let’s write a C program for tower of Hanoi problem:

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 moves the disks according to the rules we arrive at.

Also Read: What is Recursion in C?

Code Walkthrough

• Base Case: If there is one disk, it is simply brought directly from source to destination. It’s the simplest possible scenario – 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, disk 2 moves from rod A to rod B.
• Next, disk 1 moves 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 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 for Tower of Hanoi using Iterative method that implements iteration:

Output:

In this program:

• The Tower of Hanoi Iterative determines the number of moves and how to move disks based on 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 rods is calculated to generate the moves.

Comparing Recursive and Iterative Methods

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

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 for exponential time is that 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 to Avoid

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 result from forgetting the base case.
• Incorrect outputs may occur when the order of recursive calls is misplaced.

Most problems are solvable by printing or stepping through the code.

Conclusion

The Tower of Hanoi is a great puzzle that helps us think and practice recursion and iteration. This article has taught us how to solve things in C, demonstrating the beauty of recursive methods and the efficiency of iterative methods. Solving this problem makes you a sharper programmer and 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 plan to kickstart your tech career, consider pursuing Hero Vired’s Certificate Program in DevOps & Cloud Engineering, which is offered in collaboration with Microsoft.