Have you ever heard about the “Tower of Brahma”? According to a report by Édouard Lucas, there is a set of 64 gold disks on three diamond needles called the “Tower of Brahma” in the temple of Kashi Vishwanath in Varanasi, Uttar Pradesh, India.

Since the earliest days, priests have been working to find ways to transfer all the golden discs from the start needle to the end needle. The Universe may end when they succeed in moving the 64 discs without violating any of the rules framed by lord Brahma.

The popular version of this problem is the “Tower of Hanoi” puzzle. This article will help you to uncover the solution to this puzzling problem.

What is Tower of Hanoi in C?

The Tower of Hanoi is a mathematical problem. In this problem, we move a stack of disks from one peg to another. We use a temporary peg to move the disks. In this problem, we have to follow some specific rules. The puzzle consists of three pegs and a number of disks of different sizes that can be stacked onto any peg. The rules for the Tower of Hanoi puzzle are as follows:

Only 1 disk can be moved at a time.

Each move consists of taking the topmost disk from one of the stacks and placing it on top of another stack or an empty peg.

A larger disk must never be placed on top of a smaller disk.

The objective of the problem is to move the entire stack of disks from one peg (the source) to another peg (the destination), using the third peg (the auxiliary) as temporary storage.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Tower of Hanoi Problem

The fun puzzle game tower of Hanoi consists of three towers or rods and an N number of discs. The game aims to move all the discs from tower X to tower Z using tower Y. following some rules.

The main three rules of the tower of Hanoi problem are as follows:

1. You can move only one disc at a time.

2. You can move only the uppermost disc of the stack.

3. You can’t place a larger disc on top of a smaller disc.

We can solve this problem by using iterative and recursive methods.

We will cover both the recursive and iterative approaches in this article. You can visit our curated section on the Recursion topic to learn more about Recursion.

Example

Let’s start with a basic example of 3 discs to understand the problem better.

We need a base condition to solve this problem using the recursive approach.

We will consider the base case when we have only one disc, i.e., N=1.

When N = 1, move the disc from the start tower to the end tower. We can write the TOH function as follows:

TOH(1, X, Y, Z)
{
Move the topmost disc from X to Z using Y;
}

When N != 1, we can split the disc stack into two parts. All other (n-1) disks are in the second part, while the largest disc (nth) is in the first. We will call our TOH function two times for the (n-1).

Step 1: TOH(N-1, start, end, intermediate).

Step 2: Move the topmost disc from the start to the end tower.

Step 3: TOH(N-1, intermediate, start, end).

For ‘n’ discs, we can generalise the algorithm as follows:

TOH(n, X, Y, Z)
{
if(n>1)
{
TOH(n-1, X, Z, Y)
Move the topmost disc from X to Z using Y;
TOH(n-1, Y, X, Z)
}
}

Therefore when we have n=2, we can write the function as follows:

TOH(2, X, Y, Z)
{
TOH(1, X, Z, Y)
Move the topmost disc from X to Z using Y;
TOH(1, Y, X, Z)
}

When we have N = 3, we can write the algorithm as follows:

TOH(3, X, Y, Z)
{
TOH(2, X, Z, Y)
Move the topmost disc from X to Z using Y;
TOH(2, Y, X, Z)
}

The number of moves for the given function is as follows:

for n number of discs = (2n - 1)

So we can say that,

For 2 discs, the number of moves = 3

For 3 discs, the number of moves = 7

Tree Structure Diagram

To understand the algorithm better, let’s see the tree structure diagram of the TOH problem when the disc number is three.

Code in C

Here is the complete recursive code of the Tower of Hanoi in C.

// Tower of Hanoi recursive program in C void TOH(int n, char towerX, char towerY, char towerZ) { if (n == 1) { printf("\n Move the topmost disc from %c to %c", towerX, towerZ); return; }

else { TOH(n - 1, towerX, towerZ, towerY); printf("\n Move the topmost disc from %c to %c", towerX, towerZ); TOH(n - 1, towerY, towerX, towerZ); } }

Input 1

3

Output 1

Move the topmost disc from X to Z
Move the topmost disc from X to Y
Move the topmost disc from Z to Y
Move the topmost disc from X to Z
Move the topmost disc from Y to X
Move the topmost disc from Y to Z
Move the topmost disc from X to Z

Input 2

4

Output 2

Move the topmost disc from X to Y
Move the topmost disc from X to Z
Move the topmost disc from Y to Z
Move the topmost disc from X to Y
Move the topmost disc from Z to X
Move the topmost disc from Z to Y
Move the topmost disc from X to Y
Move the topmost disc from X to Z
Move the topmost disc from Y to Z
Move the topmost disc from Y to X
Move the topmost disc from Z to X
Move the topmost disc from Y to Z
Move the topmost disc from X to Y
Move the topmost disc from X to Z
Move the topmost disc from Y to Z

Complexity Analysis

Time Complexity: The time complexity of the recursive approach of the tower of Hanoi in C is O(2^{n}).

Explanation: Consider for n discs the time complexity required is T(n). We are calling the recursive function two times for (n-1) discs. Moving one disc from the start tower to the end tower is a constant time operation(suppose k1).

From these patterns, we can conclude that T(n) = O(2^{n}). It has exponential time complexity. The time requirement doubles for every single increment in the problem size.

Space Complexity: The space complexity of the recursive approach of the tower of Hanoi in C is O(n).

Explanation: Each function call's required space is independent of n, or we can say it is constant(k). The first recursive call ends when we make the second one. Therefore, we can use the first call's space for the second call.

T(n) = T(n-1) + k
T(0) = k
T(1) = 2k
T(2) = 3k
T(3) = 4k

Thus, the space complexity is O(n). The space complexity is linear for the recursive approach of the tower of Hanoi in C.

Algorithm for Iterative Approach

Calculate the total number of moves using the formula 2^{n} -1, where n is the number of discs.

If n is even Moved from the intermediate to the end tower.

For i = 1 to n if(i%3 == 0), Move the disc from the intermediate to the end tower.

else if (i%3 == 1) Move the disc from the start to the end tower.

else(i%3 == 2) Move the disc from the start to the intermediate tower.

To know more about the iterative approach in various languages, you can check out the iterative tower of Hanoi.

Code in C

Here is the complete iterative code of the Tower of Hanoi in C.

// Tower of Hanoi recursive program in C void TOH(int n, char towerX, char towerY, char towerZ) { if (n == 1) { printf("\n Move the topmost disc from %c to %c", towerX, towerZ); return; }

else { TOH(n - 1, towerX, towerZ, towerY); printf("\n Move the topmost disc from %c to %c", towerX, towerZ); TOH(n - 1, towerY, towerX, towerZ); } }

Input

3

Output

Move the disc 1 from 'X' to 'Z'
Move the disc 2 from 'X' to 'Y'
Move the disc 1 from 'Z' to 'Y'
Move the disc 3 from 'X' to 'Z'
Move the disc 1 from 'Y' to 'X'
Move the disc 2 from 'Y' to 'Z'
Move the disc 1 from 'X' to 'Z'

Complexity Analysis

Time Complexity: The time complexity of the iterative approach of the tower of Hanoi in c is O(2^{n}). The number of iterations increases exponentially with the number of discs since the iterative solution needs to produce and process every single combination of moves for n discs.

Space Complexity: The space complexity of the iterative approach of the tower of Hanoi in c is O(n) because we are using the stacks of size n. Where n is the number of discs.

The Tower of Hanoi logic is solved using a recursive algorithm. To move a stack of disks from one rod to another, move the top (n-1) disks to an auxiliary rod, move the considerable disk to the target rod, and then move the (n-1) disks from the additional rod to the target rod, follow the rules of not placing a larger disk on a smaller one.

Is it possible to solve the Tower of Hanoi in C without recursion?

Yes, one can solve the tower of Hanoi in c without recursion using three basic steps. The first step is to find the number of moves. The second and third steps describe the condition when the number of discs is even and odd, respectively.

What is the time and space complexity of the recursive approach of Tower of Hanoi in C?

The time complexity of the recursive approach of the tower of Hanoi in C is O(2^{n}). The space complexity of the recursive approach of the tower of Hanoi in C is O(n).

What is the time and space complexity of the iterative approach of Tower of Hanoi in C?

The time complexity of the iterative approach of the tower of Hanoi in C is O(2^{n}). The space complexity of the iterative approach of the tower of Hanoi in C is O(n), as we use stack to solve the problem.

Conclusion

In this article, we extensively discussed the tower of Hanoi problem, algorithm, and code for the tower of Hanoi in C.

We hope this blog has helped you with your interview. We recommend you visit our articles on different topics of C, such as