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.

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.

Get curriculum highlights, career paths, industry insights and accelerate your technology journey.

Download brochure

Concept Behind 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 3 disks, the minimum number of moves will be:
Moves = 2^3 - 1 = 7

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.

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:

#include <stdio.h>
void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {
if (n == 1) {
// Rephrased sentence for single disk move
printf("Disk 1 is being relocated from rod %c to rod %c.n", from_rod, to_rod);
return;
}
towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);
// Rephrased sentence for general disk move
printf("Disk %d is being shifted from rod %c to rod %c.n", n, from_rod, to_rod);
towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
}
int main() {
int n = 3;
towerOfHanoi(n, 'A', 'C', 'B'); // Call the recursive function
return 0;
}

Output:

Disk 1 is being relocated from rod A to rod C.
Disk 2 is being shifted from rod A to rod B.
Disk 1 is being relocated from rod C to rod B.
Disk 3 is being shifted from rod A to rod C.
Disk 1 is being relocated from rod B to rod A.
Disk 2 is being shifted from rod B to rod C.
Disk 1 is being relocated from rod A to rod C.

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.

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:

#include <stdio.h>
#include <math.h>
void moveDisk(char from_rod, char to_rod, int disk) {
// Rephrased output sentence
printf("In this move, we are shifting disk %d from rod %c and placing it on rod %c.n", disk, from_rod, to_rod);
}
void towerOfHanoiIterative(int n) {
int total_moves = pow(2, n) - 1; // Total moves required
char rods[] = {'A', 'B', 'C'}; // Names of the rods
// If the number of disks is even, swap the destination and auxiliary rods
if (n % 2 == 0) {
char temp = rods[1];
rods[1] = rods[2];
rods[2] = temp;
}
for (int i = 1; i <= total_moves; i++) {
int from_rod = (i & i - 1) % 3; // Source rod
int to_rod = ((i | i - 1) + 1) % 3; // Destination rod
// Move the disk and print the rephrased output
moveDisk(rods[from_rod], rods[to_rod], (i % 3) + 1);
}
}
int main() {
int n = 3;
towerOfHanoiIterative(n); // Call the iterative function
return 0;
}

Output:

In this move, we are shifting disk 2 from rod A and placing it on rod C.
In this move, we are shifting disk 3 from rod A and placing it on rod B.
In this move, we are shifting disk 1 from rod C and placing it on rod B.
In this move, we are shifting disk 2 from rod A and placing it on rod C.
In this move, we are shifting disk 3 from rod B and placing it on rod A.
In this move, we are shifting disk 1 from rod B and placing it on rod C.
In this move, we are shifting disk 2 from rod A and placing it on rod C.

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.

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.

FAQs

What is the Tower of Hanoi in a C program?

They use the Tower of Hanoi problem, a mathematical problem. In this problem, we need to move a stack of disks from one peg to another. To move the disks, we use a temporary peg. Upcoming tasks in this problem include the following: The puzzle involves three pegs, with various-sized disks to be stacked on any peg as it is put together.

How does the Tower of Hanoi work?

The Tower of Hanoi recursive algorithm involves the following major steps: Disk rotation recurse moves disks from the source rod to the auxiliary rod. It moves the nth disk from the source rod to the target rod. Finally, we again recursively move the disks from the auxiliary rod to the target rod.

How long does it take (steps) to complete the Tower of Hanoi puzzle?

This formula is S, the number of steps, and N, the number of discs. Now if the tower had five discs then the formula is 2⁵ - 1, which is 31. Since the puzzle must be solved in 31 steps at most, this is why. It would take just 15 steps to play it if it had four discs — and just 7 if it had three.

How fast and how much memory does the recursive approach to Tower of Hanoi take in C?

The recursive approach of time complexity for a tower of Hanoi in C is O(2n). The recursive approach of the space complexity of the tower of Hanoi problem in C is an O(n).

Hero Vired is a leading LearnTech company dedicated to offering cutting-edge programs in collaboration with top-tier global institutions. As part of the esteemed Hero Group, we are committed to revolutionizing the skill development landscape in India. Our programs, delivered by industry experts, are designed to empower professionals and students with the skills they need to thrive in today’s competitive job market.