---
**Meta title:** Tower of Hanoi recursion algorithm explained (with C++ code & complexity)
**Meta description:** Tower of Hanoi is a classic recursion puzzle. Learn the algorithm, recurrence relation, time complexity O(2^N), and see a working C++ implementation.
**Estimated read time:** 9 minutes
**Primary persona:** Engineering Manager / Technical hiring lead evaluating recursion fundamentals as part of candidate assessment design.
---
Tower of Hanoi is a mathematical recursion puzzle invented by French mathematician Édouard Lucas in 1883, in which N disks must be moved across three pegs in the minimum number of moves. For engineering managers and technical hiring leads, the Tower of Hanoi recursion algorithm is one of the cleanest ways to evaluate whether a candidate can decompose a problem, reason about base cases, and analyze exponential time complexity — all skills that surface repeatedly in real engineering work. This article explains the algorithm, the math behind it, and how it maps to the kinds of problem-solving signals you may want to assess in technical interviews.
## History of Tower of Hanoi
While Lucas is credited with introducing — and popularizing — the puzzle in the Western world in 1883, its mythological backstory predates that publication.
According to legend, an ancient temple (some accounts place it in India, others in Vietnam, which is sometimes cited as the origin of the "Hanoi" name) has a large room with three towers surrounded by 64 golden disks. According to the same legend, these disks are continuously moved by priests in the temple, and when the last move of the puzzle is completed, the world will end.
According to the legend, the priests follow an immutable rule by Lord Brahma of moving these disks one at a time. Hence this puzzle is often called the Tower of Brahma puzzle.
Tower of Hanoi is one of the classic problems to look at when learning recursion. It is useful for understanding how recursive solutions are arrived at and how parameters for recursion are structured.
## What is the game of Tower of Hanoi?
Tower of Hanoi consists of three pegs or towers with *n* disks placed one over the other. The objective of the puzzle is to move the stack to another peg following these simple rules:
1. Only one disk can be moved at a time.
2. No larger disk can be placed on top of a smaller disk.
[](https://www.hackerearth.com/challenges/?utm_source=blog&utm_medium=strip)
Before we proceed, let's understand recursion.
### What is recursion?
Recursion is when a function calls itself to solve a smaller instance of the same problem until it reaches a base case.
An informal way to picture it: in the movie *Inception*, Leonardo has a dream, in that dream he has another dream, in that dream he has yet another dream, and so on — each layer is the same kind of experience nested inside the previous one. In code terms, that's a function `dream()` that calls itself.
**Pseudocode (illustrative, not runnable):**
// pseudocode function dream() print "Dreaming" dream()
Recursion is useful for solving problems that can be broken down into smaller problems of the **same kind**.
When solving problems using recursion, several things must be considered. Here is the pseudo code for finding the factorial of a given number X using recursion.
**Pseudocode (illustrative, not runnable):**
// pseudocode function factorial(x) if x is 0 // base case return 1 return x*factorial(x-1) // break into smaller problem(s)
A more detailed explanation of recursion is available in this [recursion and backtracking tutorial](https://www.hackerearth.com/practice/basic-programming/recursion/recursion-and-backtracking/tutorial/). For a foundational overview, see also the [Wikipedia entry on recursion in computer science](https://en.wikipedia.org/wiki/Recursion_(computer_science)).
## Tower of Hanoi recursion algorithm explained
The Tower of Hanoi recursion algorithm solves the puzzle by reducing each N-disk problem into two (N-1)-disk subproblems plus one single move.
Take an example with 2 disks: Disk 1 on top of Disk 2 at peg A. The target is to move both these disks to peg B.
The steps are: move Disk 1 from peg A to peg C, then move Disk 2 from peg A to peg B, and finally move Disk 1 from peg C to peg B. This solution takes 3 steps.
The same 3-step pattern can be used to move the stack from peg B to any other peg.
Now consider 3 disks — 1, 2, and 3 — stacked on peg A. To move the stack to peg B, disk 3 must be exposed, which means disks 1 and 2 have to be moved to peg C first.
By applying the previous 3-step subset without breaking the rules, you can move disks 1 and 2 to peg C, leaving disk 3 exposed.
[](https://media.hackerearth.com/blog/wp-content/uploads/2016/12/tower-02-1.jpg)
Now, recursively move disk 3 from peg A to peg B. Then move disk 1 from peg C to peg A. After that, disk 2 can be moved on top of disk 3 at peg B. The puzzle is finally completed by moving disk 1 from peg A on top of disks 2 and 3 at peg B.
**What if you have 4 disks?**
* Recursively solve the problem of moving disks 1, 2, and 3 from peg A to peg C
* Move disk 4 from A to B
* Recursively solve the problem of moving disks 1, 2, and 3 from peg C to peg B
A pattern emerges: with each additional disk, the same recursive structure applies. While the 3-disk puzzle requires 7 steps, the 4-disk puzzle requires 7 + 1 + 7 = 15 steps.
**4-disk visualization**
The algorithm in plain terms:
* Create a function `tower` with `int a` (number of disks), `char from` (source peg), `char aux` (auxiliary peg), and `char to` (destination peg).
* If `a == 1`, move the disk directly from the source peg to the destination peg (base case).
* Otherwise, recursively move `a-1` disks from `from` to `aux`, move disk `a` from `from` to `to`, and then recursively move the `a-1` disks from `aux` to `to`.
```cpp
void tower(int a, char from, char aux, char to) {
if (a == 1) {
std::cout << "\t\tMove disc 1 from " << from << " to " << to << "\n";
return;
}
tower(a - 1, from, to, aux);
std::cout << "\t\tMove disc " << a << " from " << from << " to " << to << "\n";
tower(a - 1, aux, from, to);
}
Calling the function from main:
#include <iostream>
int main() {
int n;
std::cout << "\n\t\t*****Tower of Hanoi*****\n";
std::cout << "\t\tEnter number of discs : ";
std::cin >> n;
std::cout << "\n\n";
tower(n, 'A', 'B', 'C');
return 0;
}
Tower of Hanoi maths and complexity analysis explained
The minimum number of moves required to solve a Tower of Hanoi puzzle with N disks is 2^N − 1, which means the number of moves roughly doubles each time a disk is added.
The sequence of minimum moves (1, 3, 7, 15, 31, …) is catalogued as OEIS sequence A000225.
Proving the move count
The question is: what is the minimum number of moves (aN) required to move all N disks to another peg?
One can already see that a1 = 1, a2 = 3, a3 = 7, and so on.
For a given N, the minimum-step procedure is:
- Move the top N−1 disks to an intermediate peg.
- Move the bottom disk to the destination peg.
- Move the N−1 disks from the intermediate peg to the destination peg.
Therefore, the recurrence relation is:
a1 = 1; aN = 2 * a(N−1) + 1; N ≥ 2
Solving the recurrence iteratively yields aN = 2^N − 1.
Time and space complexity
- Time complexity: O(2^N). Each recursive call generates two more calls until the base case, producing 2^N − 1 total moves.
- Space complexity: O(N). The recursion stack reaches a depth equal to the number of disks.
Trade-offs: when recursion may not be the right choice
Although recursion expresses the Tower of Hanoi solution very cleanly, it is not always the optimal implementation choice. For large N, recursive call stacks can hit language- or platform-specific stack-depth limits and cause overflow before exhaustive enumeration finishes. An iterative implementation using an explicit stack data structure produces the same sequence of moves with more predictable memory behavior and is often preferred in production code or when N is large. In interview settings, candidates who can articulate both approaches — and explain when to pick which — tend to demonstrate stronger problem-solving signal than those who can only recite the recursive form.
The 64-disk prophecy
Suppose the priests can move one disk per second, continuously, 24 hours a day. At that rate, completing 2^64 − 1 moves — that is, 18,446,744,073,709,551,615 moves — would take approximately 585 billion years. (This figure is a direct arithmetic consequence of 2^64 − 1 seconds; see the Wikipedia entry on the Tower of Hanoi for the standard formulation.)
For reference, the Milky Way is estimated to be around 13.6 billion years old, and Earth is approximately 4.54 billion years old — so the prophecy has a generous timeline.
Tower of Hanoi practice problem in C++
Note: The classic Tower of Hanoi is a recursion problem, not a dynamic programming problem. The sample below comes from a related HackerEarth challenge that uses a variant of the puzzle's framing — stacking disks under radius and height constraints — and is solved with a dynamic programming approach similar to the Longest Increasing Subsequence. It is included here as a worked example of how puzzle framings can be adapted into different algorithmic problems, not as an implementation of the standard Tower of Hanoi recursion.
Here is the practice question from HackerEarth.
Q. Bob and Alice like to play the game Tower of Hanoi. One day Alice challenges Bob to build the tallest tower from a set of disks of different heights and radii. The tower can be built by stacking disks on top of each other. To put disk A on top of disk B, the radius and height of A must be strictly smaller than those of B. Help Bob win the challenge.
C++ solution (DP variant):
#include <bits/stdc++.h>
#define lli long long
using namespace std;
lli dp[202];
int main()
{
int t, n;
lli x, y;
cin >> t;
assert(t <= 10);
while (t--) {
cin >> n;
assert(n <= 200);
vector<pair<lli, lli>> v;
for (int i = 0; i < n; i++) {
cin >> x >> y;
assert(x <= 1000000000);
assert(y <= 1000000000);
v.push_back(make_pair(x, y));
}
sort(v.begin(), v.end());
dp[0] = v[0].second;
lli ans = v[0].second;
for (int i = 1; i < n; i++) {
dp[i] = v[i].second;
for (int j = 0; j < i; j++) {
if (v[i].second > v[j].second && v[i].first > v[j].first)
dp[i] = max(dp[i], dp[j] + v[i].second);
}
ans = max(ans, dp[i]);
}
cout << ans << endl;
}
return 0;
}
Key takeaways
- Tower of Hanoi recursion solves N disks in a minimum of 2^N − 1 moves.
- The recurrence relation is aN = 2 · a(N−1) + 1, with base case a1 = 1.
- Time complexity is O(2^N); space complexity is O(N) (recursion stack depth).
- The problem is a canonical teaching example for recursion, base cases, and recurrence-relation analysis — common signals to evaluate in technical screens.
- Iterative implementations can avoid stack-depth limitations for large N and are worth knowing alongside the recursive form.
FAQs
What is the time complexity of Tower of Hanoi recursion? The time complexity is O(2^N), because each recursive call produces two further calls and the total number of moves required to solve the puzzle with N disks is 2^N − 1.
What is the space complexity of Tower of Hanoi recursion? The space complexity is O(N) due to the depth of the recursion call stack, which equals the number of disks.
How does recursion work in Tower of Hanoi? Each N-disk problem is decomposed into two (N−1)-disk subproblems and one move of the largest disk: move N−1 disks to the auxiliary peg, move the largest disk to the destination, then move the N−1 disks onto the destination.
What is the minimum number of moves for N disks? The minimum number of moves is 2^N − 1. For example, 3 disks require 7 moves and 4 disks require 15 moves.
What is the base case in Tower of Hanoi recursion? The base case is when N = 1 — a single disk is simply moved from the source peg directly to the destination peg without further recursion.
Is Tower of Hanoi a dynamic programming problem? No. The classic Tower of Hanoi is solved with recursion (or equivalently, an iterative algorithm), not dynamic programming. There are no overlapping subproblems being memoized in the standard solution.
Next steps
If you're evaluating candidates on recursion and algorithmic problem-solving, consider running a structured technical assessment that surfaces these signals at scale. Explore HackerEarth Assessments to design role-aligned coding tests, or browse HackerEarth Challenges to see how recursion problems are presented in competitive settings. For self-paced practice, CodeMonk offers structured algorithm tracks.
Want more algorithm explainers and technical hiring insights? Subscribe to The HackerEarth Blog. ```
