Home Newsroom Tower of Hanoi: Recursive Algorithm, Rules, Steps, Code & Complexity Explained

Tower of Hanoi: Recursive Algorithm, Rules, Steps, Code & Complexity Explained

Tower of Hanoi is a classic recursion problem that explains how to break a complex task into smaller subproblems. This guide covers its rules, recursive algorithm, code in Python, C++, Java, and C, dry runs, the 2ⁿ − 1 minimum-move formula, time and space complexity, common mistakes, and interview questions.

0 min read

Tower of Hanoi: Recursive Algorithm, Rules, Steps, Code & Complexity Explained

f you've started learning recursion in programming, chances are you've already come across the Tower of Hanoi.

At first, it looks like a simple puzzle: three rods, a few disks and a set of rules about how you can move them. But there's a reason it appears so often in DSA classes, coding tutorials and technical interviews.

Tower of Hanoi makes you think recursively.

Instead of trying to solve the entire problem at once, you break it into a smaller version of the same problem, solve that, and use the result to solve the original one.

There's also a neat mathematical result behind it: for n disks, the minimum number of moves is 2ⁿ − 1.

Let's understand how it works, why recursion fits the problem so well, and how to implement it in Python, C++, Java and C.

What Is the Tower of Hanoi?

The Tower of Hanoi is a mathematical puzzle with three rods and a stack of disks of different sizes.

All the disks start on one rod, arranged with the largest at the bottom and the smallest at the top.

The goal is to move the entire stack to another rod while following a few simple rules:

You can move only one disk at a time.
You can move only the top disk from a rod.
You can never place a larger disk on top of a smaller disk.

It sounds easy with two or three disks. The interesting part is what happens when you keep increasing the number of disks.

That's where recursion comes in.

Tower of Hanoi Rules

Rule	Why It Matters
Move one disk at a time	Every solution has to follow a specific sequence of individual moves
Only the top disk can move	You can't access a disk buried underneath another disk
Never place a larger disk on a smaller one	This creates the main constraint of the puzzle
Use only three rods	The limited space makes the recursive solution necessary

How Does the Tower of Hanoi Work?

The easiest way to understand the puzzle is to start with two disks.

Suppose:

Rod A = Source
Rod B = Auxiliary
Rod C = Destination

You want to move both disks from A to C.

Here's what happens:

Move	Disk	From	To
1	Disk 1	A	B
2	Disk 2	A	C
3	Disk 1	B	C

Why this order?

You can't move the larger disk until the smaller disk is out of the way.

Once the larger disk reaches C, the smaller disk can be placed on top of it.

And that's essentially the entire idea behind Tower of Hanoi:

Move the smaller disks out of the way → move the largest disk → move the smaller disks back.

For more disks, we simply repeat this same idea recursively.

How Does the Tower of Hanoi Use Recursion?

This is where the puzzle gets interesting.

Recursion means solving a problem by solving a smaller version of the same problem until you reach a simple case that can be solved directly.

For Tower of Hanoi, that smaller problem is obvious:

If you know how to move n − 1 disks, you can figure out how to move n disks.

To move n disks from Source to Destination:

Step 1: Move n − 1 disks

Move the top n − 1 disks from Source to Auxiliary, using Destination as the temporary rod.

Step 2: Move the largest disk

Now the largest disk is free.

Move it directly from Source to Destination.

Step 3: Move n − 1 disks again

Finally, move the n − 1 disks from Auxiliary to Destination, using Source as the helper.

And those first and third steps are themselves Tower of Hanoi problems involving n − 1 disks.

That's recursion.

The base case is n = 1. If there's only one disk, just move it directly from Source to Destination.

Tower of Hanoi Recursion Example

Let's take 3 disks and move them from A to C using B as the auxiliary rod.

The recursive call can be written as:

T(n, source, auxiliary, destination)

For three disks:

T(3, A, B, C)

├── T(2, A, C, B)

│ ├── T(1, A, B, C)

│ ├── Move disk 2: A → B

│ └── T(1, C, A, B)

│

├── Move disk 3: A → C

│

└── T(2, B, A, C)

├── T(1, B, C, A)

├── Move disk 2: B → C

└── T(1, A, B, C)

If you follow the calls from left to right, the actual moves are:

Disk 1: A → C
Disk 2: A → B
Disk 1: C → B
Disk 3: A → C
Disk 1: B → A
Disk 2: B → C
Disk 1: A → C

That's 7 moves for 3 disks.

Tower of Hanoi Algorithm

Here's the basic pseudocode:

Algorithm Hanoi(n, source, auxiliary, destination):

if n == 1:

move disk 1 from source to destination

return

Hanoi(n - 1, source, destination, auxiliary)

move disk n from source to destination

Hanoi(n - 1, auxiliary, source, destination)

There are two things to notice here.

First, the base case stops the recursion when only one disk remains.

Second, every recursive call works with n − 1 disks, so the problem keeps getting smaller.

The source, auxiliary and destination rods also change positions between recursive calls. That's one of the easiest things to get wrong when you're first learning the problem.

Tower of Hanoi Code

The logic stays the same regardless of the programming language.

Python

def tower_of_hanoi(n, source, auxiliary, destination):

if n == 1:

print(f"Move disk 1 from {source} to {destination}")

return

tower_of_hanoi(n - 1, source, destination, auxiliary)

print(f"Move disk {n} from {source} to {destination}")

tower_of_hanoi(n - 1, auxiliary, source, destination)

# Solve for 3 disks

tower_of_hanoi(3, 'A', 'B', 'C')

C++

#include <iostream>

using namespace std;

void towerOfHanoi(int n, char source, char auxiliary, char destination) {

if (n == 1) {

cout << "Move disk 1 from "

<< source << " to "

<< destination << endl;

return;

}

towerOfHanoi(n - 1, source, destination, auxiliary);

cout << "Move disk " << n << " from "

<< source << " to "

<< destination << endl;

towerOfHanoi(n - 1, auxiliary, source, destination);

}

int main() {

int n = 3;

towerOfHanoi(n, 'A', 'B', 'C');

return 0;

}

Java

public class TowerOfHanoi {

static void towerOfHanoi(

int n,

char source,

char auxiliary,

char destination

) {

if (n == 1) {

System.out.println(

"Move disk 1 from " +

source + " to " +

destination

);

return;

}

towerOfHanoi(

n - 1,

source,

destination,

auxiliary

);

System.out.println(

"Move disk " + n +

" from " + source +

" to " + destination

);

towerOfHanoi(

n - 1,

auxiliary,

source,

destination

);

}

public static void main(String[] args) {

int n = 3;

towerOfHanoi(n, 'A', 'B', 'C');

}

C

#include <stdio.h>

void towerOfHanoi(

int n,

char source,

char auxiliary,

char destination

) {

if (n == 1) {

printf(

"Move disk 1 from %c to %c\n",

source,

destination

);

return;

}

towerOfHanoi(

n - 1,

source,

destination,

auxiliary

);

printf(

"Move disk %d from %c to %c\n",

source,

destination

);

towerOfHanoi(

n - 1,

auxiliary,

source,

destination

);

}

int main() {

int n = 3;

towerOfHanoi(n, 'A', 'B', 'C');

return 0;

}

All four implementations follow the same structure: base case → move n − 1 disks → move the largest disk → move n − 1 disks again.

Tower of Hanoi Dry Run for 3 Disks

Let's put the code into action.

For:

tower_of_hanoi(3, 'A', 'B', 'C')

the output is:

Move	Disk	From	To
1	1	A	C
2	2	A	B
3	1	C	B
4	3	A	C
5	1	B	A
6	2	B	C
7	1	A	C

So, 3 disks require 7 moves.

Notice something interesting: the largest disk moves only once. Disk 2 moves twice, while disk 1 moves four times.

That pattern is what eventually gives us the famous 2ⁿ − 1 formula.

Tower of Hanoi Formula

The minimum number of moves required for n disks is:

2ⁿ − 1

We can derive this from the recursive structure.

Let M(n) represent the minimum number of moves for n disks.

To move n disks:

Move n − 1 disks → M(n − 1)
Move the largest disk → 1
Move n − 1 disks again → M(n − 1)

So:

M(n) = 2M(n − 1) + 1

With:

M(1) = 1

Solving this recurrence gives:

M(n) = 2ⁿ − 1

Number of Disks	Minimum Moves
1	1
2	3
3	7
4	15
5	31
10	1,023

The important thing here is that the number of moves grows exponentially.

For example, 10 disks need 1,023 moves. With 20 disks, you're already at 2,097,151 moves.

Why Does the Tower of Hanoi Have 64 Disks in Its Famous Legend?

Tower of Hanoi is commonly associated with a story about 64 golden disks and monks who must move them between three rods.

The story is usually attributed to French mathematician Édouard Lucas, who introduced the puzzle in 1883.

The legend says that when the monks finish moving all 64 disks, the world will end.

Thankfully, there's no need to worry.

The mathematics behind the puzzle is real, but the legend isn't.

For 64 disks:

2⁶⁴ − 1 = 18,446,744,073,709,551,615 moves.

Even at one move per second, that's an unimaginably long time.

Tower of Hanoi Time Complexity

Time Complexity: O(2ⁿ)

The recursive algorithm makes two recursive calls for almost every value of n.

Since the total number of moves is:

2ⁿ − 1

the time complexity is:

O(2ⁿ)

This is exponential growth, which means the number of operations increases extremely quickly as the number of disks increases.

Space Complexity: O(n)

The space complexity is different.

Although the algorithm performs exponentially many moves, the recursive call stack only goes as deep as n.

Therefore:

Space Complexity = O(n)

This is an important distinction: time measures the total work; space measures the maximum memory used at one time.

Recursive vs Iterative Tower of Hanoi

The Tower of Hanoi can also be solved without recursion.

An iterative solution can simulate the recursive call stack using an explicit stack or use a known pattern for moving the smallest disk.

Both approaches still require 2ⁿ − 1 moves, because that's a property of the puzzle itself.

Factor	Recursive	Iterative
Approach	Uses recursive calls	Uses loops and explicit state
Readability	Easier to understand	More difficult initially
Implementation	Short and clean	Requires more bookkeeping
Time Complexity	O(2ⁿ)	O(2ⁿ)
Space Complexity	O(n)	O(1) or O(n), depending on approach
Learning Value	Excellent for understanding recursion	Useful for understanding how recursion can be replaced

For someone learning recursion, the recursive approach is the better starting point because it follows the mathematical structure of the problem directly.

Common Mistakes When Solving Tower of Hanoi

Tower of Hanoi is simple once the pattern clicks, but beginners usually make the same few mistakes.

1. Mixing up the rods

The source, auxiliary and destination positions change between recursive calls. Mixing them up can completely change the move sequence.

2. Forgetting the base case

Without a proper base case, the recursion won't stop.

3. Moving the largest disk too early

The largest disk can move only after every smaller disk has been moved out of its way.

4. Moving more than one disk at a time

Every move must involve exactly one disk.

5. Placing a larger disk on a smaller one

This immediately violates the rules.

6. Getting the recursive order wrong

The first recursive call must finish before the largest disk is moved.

7. Thinking the number of moves is roughly 2n

It's not linear or simply proportional to the number of disks. It grows exponentially as 2ⁿ − 1.

8. Confusing recursion depth with total moves

The call stack grows to O(n), not O(2ⁿ), even though the algorithm performs 2ⁿ − 1 moves.

Why Is the Tower of Hanoi Important in Coding Interviews?

Tower of Hanoi isn't necessarily asked in every technical interview, but it's a popular problem for testing whether someone actually understands recursion.

It brings several concepts together:

Recursion
Problem decomposition
Base cases
Call stacks
Mathematical reasoning
Time and space complexity

The real value isn't memorizing the code.

It's being able to explain why the code works.

That same reasoning becomes useful when solving other recursive DSA problems and technical assessments.

For candidates preparing for technical hiring, technical assessments and online coding assessments can also test similar problem-solving and programming skills.

technical assessments and online coding assessments are natural internal links here because they connect the concept of coding practice to actual technical assessment environments.

FAQs

What is the Tower of Hanoi?

Tower of Hanoi is a classic puzzle involving three rods and a set of differently sized disks. The objective is to move the complete stack from one rod to another while following the rules that only one disk can move at a time and a larger disk can never be placed on a smaller one.

What are the rules of the Tower of Hanoi?

There are three main rules: move only one disk at a time, move only the top disk from any rod, and never place a larger disk on top of a smaller disk.

Why is the Tower of Hanoi a recursion problem?

Moving n disks requires first moving n − 1 disks out of the way, then moving the largest disk, and finally moving those n − 1 disks again. Since the same problem keeps appearing with a smaller input, recursion is a natural fit.

What is the Tower of Hanoi formula?

The minimum number of moves is 2ⁿ − 1. This comes from the recurrence M(n) = 2M(n − 1) + 1, with M(1) = 1.

What is the minimum number of moves for n disks?

The minimum is 2ⁿ − 1 moves. For example, 3 disks need 7 moves, 5 disks need 31 moves and 10 disks need 1,023 moves.

What is the time complexity of Tower of Hanoi?

The time complexity is O(2ⁿ) because the algorithm produces 2ⁿ − 1 total moves.

What is the space complexity of the Tower of Hanoi?

The recursive solution has O(n) space complexity because the maximum recursion depth is n.

How do you solve the Tower of Hanoi using recursion?

Move n − 1 disks from Source to Auxiliary, move the largest disk from Source to Destination, and then move the n − 1 disks from Auxiliary to Destination. Repeat this process until only one disk remains.

Can the Tower of Hanoi be solved without recursion?

Yes. It can be solved iteratively using an explicit stack or a known cyclic pattern for the disk movements.

What is the Tower of Hanoi used for?

It is mainly used to teach recursion, problem decomposition, call-stack behaviour and exponential complexity. It is also commonly used for DSA practice and coding interview preparation.

How many moves are needed for 3 disks?

7 moves, calculated using 2³ − 1.

How many moves are needed for 64 disks?

18,446,744,073,709,551,615 moves, calculated using 2⁶⁴ − 1.

Conclusion

Tower of Hanoi may look like a simple puzzle, but it teaches one of the most important ideas in programming: how to break a big problem into smaller versions of the same problem.

Once you understand the recursive pattern, the rest starts falling into place, the base case, the call stack, the 2ⁿ − 1 formula and the O(2ⁿ) time complexity.

So don't just memorize the code.

Understand why the three-step recursive approach works.

That understanding will help you far beyond Tower of Hanoi, especially when you start solving more complex recursion and DSA problems.

Edited by

Mayank Tyagi

SEO & Content Marketing Specialist

Mayank Tyagi is a digital marketing expert with 15+ years of experience in SEO, content marketing, and performance optimization. He focuses on driving organic traffic, improving search engine rankings, and building scalable content strategies for long-term growth.