Tower of Hanoi Using Recursion: Algorithm, C++ Code & Complexity
The Tower of Hanoi recursion algorithm solves an N-disk puzzle by reducing it to two (N−1)-disk subproblems plus one move of the largest disk — a pattern that makes it the canonical teaching example for recursion in C++, Python, and C. This guide walks through the Tower of Hanoi algorithm step by step, shows runnable code in three languages, derives the 2^N − 1 move count, and covers the iterative alternative for large N. Engineering managers calibrating a recursion rubric will find a short section at the end on what each part of a candidate's answer signals about seniority.
History of the Tower of Hanoi game
French mathematician Édouard Lucas introduced and popularized the puzzle in the Western world in 1883, but its mythological backstory predates that publication.
The puzzle's name comes from Hanoi, Vietnam. The accompanying Brahma legend, however, is set in a temple in Benares (modern-day Varanasi), India, where — according to the story — a large room contains three towers surrounded by 64 golden disks. Priests in the temple continuously move the disks according to an immutable rule set down by Lord Brahma: one disk at a time, never a larger disk on top of a smaller one. When the last move is completed, the legend says, the world will end. For this reason the puzzle is sometimes called the Tower of Brahma.
What is the Tower of Hanoi game?
The Tower of Hanoi game consists of three pegs with n disks placed one over the other. The objective is to move the stack to another peg following two rules:
- Only one disk can be moved at a time.
- No larger disk can be placed on top of a smaller disk.
The Tower of Hanoi problem is a canonical recursion exercise because the rules force you to think in terms of subproblems rather than step-by-step moves. The core question is: can you see the (N−1) sub-stack as a unit, rather than tracing 2^N − 1 discrete moves in your head?
Recursion in one line
Recursion is when a function calls itself to solve a smaller instance of the same problem until it reaches a base case. For Tower of Hanoi recursion, the base case is the single most important moment to get right: when N == 1, move one disk directly. If you want a wider refresher on when recursion is the right tool, HackerEarth's writeup on why to study data structures and algorithms and the Wikipedia entry on recursion in computer science both give the formal definition.
What is the trick for solving the Towers of Hanoi?
The trick is a reframe: stop thinking about individual moves and start thinking about the top (N−1) disks as a single unit you can relocate. Once you accept that moving N−1 disks between any two pegs is a solved problem (by induction), the N-disk case collapses to three steps — relocate the top N−1 disks, move the bottom disk, relocate the N−1 disks back on top. People who find the puzzle hard are usually tracking individual moves; people who find it easy are tracking sub-stacks.
What is the Tower of Hanoi formula?
The minimum number of moves for a Tower of Hanoi puzzle with N disks is 2^N − 1. For N = 3 that is 7; for N = 4 it is 15; for N = 10 it is 1,023. The move count roughly doubles each time a disk is added, which is why the puzzle is the standard example of exponential growth in an algorithms course.
Can you explain the recursive Tower of Hanoi algorithm?
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 of the largest disk. In plain terms: to move N disks from peg A to peg B using peg C as helper, first move N−1 disks from A to C, then move the largest disk from A to B, then move the N−1 disks from C to B. The base case is a single disk, which moves directly.
Take 2 disks: Disk 1 on top of Disk 2 at peg A. Target: move both to peg B.
The steps are: move Disk 1 from A to C, move Disk 2 from A to B, move Disk 1 from C to B. Three steps, matching 2^2 − 1 = 3.
Now 3 disks on peg A. To move the stack to peg B, disk 3 must be exposed. That means disks 1 and 2 have to be relocated to peg C first — which is itself a 2-disk subproblem.
Once disks 1 and 2 are on peg C, move disk 3 from A to B. Then apply the same 2-disk procedure to move disks 1 and 2 from C to B. Total: 7 moves (2^3 − 1).
What if you have 4 disks?
- Recursively move disks 1, 2, 3 from A to C (7 moves)
- Move disk 4 from A to B (1 move)
- Recursively move disks 1, 2, 3 from C to B (7 moves)
That's 7 + 1 + 7 = 15 moves, matching 2^4 − 1.
4-disk visualization
The algorithm in plain terms:
- Define
tower(a, from, aux, to)whereais the disk count,fromis the source peg,auxis the helper, andtois the destination. - Base case: if
a == 1, move the disk directly fromfromtoto. - Recursive case: move
a−1disks fromfromtoaux, move diskafromfromtoto, then move thea−1disks fromauxtoto.
Tower of Hanoi in C++
The complete, compilable version — forward declaration included so both snippets below link as a single translation unit:
#include <iostream>
// forward declaration so main() can call tower()
void tower(int a, char from, char aux, char to);
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);
}
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 recursion in Python
The same shape — base case, two recursive calls, one direct move — carries straight over to Python:
def tower(a, src, aux, dst):
if a == 1:
print(f"Move disc 1 from {src} to {dst}")
return
tower(a - 1, src, dst, aux)
print(f"Move disc {a} from {src} to {dst}")
tower(a - 1, aux, src, dst)
n = int(input("Enter number of discs: "))
tower(n, 'A', 'B', 'C')
Tower of Hanoi in C
The C version differs only in printf syntax and the lack of std:: qualifiers:
#include <stdio.h>
void tower(int a, char from, char aux, char to) {
if (a == 1) {
printf("Move disc 1 from %c to %c\n", from, to);
return;
}
tower(a - 1, from, to, aux);
printf("Move disc %d from %c to %c\n", a, from, to);
tower(a - 1, aux, from, to);
}
int main(void) {
int n;
printf("Enter number of discs: ");
scanf("%d", &n);
tower(n, 'A', 'B', 'C');
return 0;
}
If you can write idiomatic recursion in one of these languages, porting it to the others is mostly syntax substitution. Stumbles when porting usually point to the recursion model, not the language.
Tower of Hanoi recursion time complexity and math
The minimum number of moves required to solve a Tower of Hanoi problem with N disks is 2^N − 1. The move count roughly doubles each time a disk is added.
The sequence (1, 3, 7, 15, 31, …) is catalogued as OEIS sequence A000225.
Proving the move count
Let aN be the minimum number of moves for N disks. By inspection, a1 = 1, a2 = 3, a3 = 7.
The minimum-step procedure for any N 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.
So the recurrence relation is:
a1 = 1; aN = 2 · a(N−1) + 1; N ≥ 2
Solving iteratively yields the closed form aN = 2^N − 1.
Tower of Hanoi recursion time complexity
- Time complexity: O(2^N). Each call generates two more until the base case, producing 2^N − 1 total moves.
- Space complexity: O(N). The recursion stack depth equals the number of disks.
The stack depth is linear while the move count is exponential because the recursion is depth-first: at any point only one chain of recursive calls is open, from the root call down to the current base case. The exponential blowup is in the total number of calls over time, not in the depth of any single chain.
Iterative Tower of Hanoi with an explicit stack
For large N, recursive call stacks can hit language- or platform-specific depth limits. An iterative implementation using an explicit stack produces the same move sequence with more predictable memory behavior:
#include <iostream>
#include <stack>
#include <tuple>
void towerIterative(int n, char from, char aux, char to) {
std::stack<std::tuple<int, char, char, char, int>> work;
work.push({n, from, aux, to, 0});
while (!work.empty()) {
auto [a, src, hlp, dst, stage] = work.top();
work.pop();
if (a == 1) {
std::cout << "Move disc 1 from " << src << " to " << dst << "\n";
continue;
}
if (stage == 0) {
// Push in reverse of execution order
work.push({a - 1, hlp, src, dst, 0}); // step 3
work.push({a, src, hlp, dst, 1}); // step 2 (print)
work.push({a - 1, src, dst, hlp, 0}); // step 1
} else {
std::cout << "Move disc " << a << " from " << src << " to " << dst << "\n";
}
}
}
There is also a non-stack iterative form based on alternating "legal moves" between pegs in a fixed order, but the explicit-stack version mirrors the recursive algorithm move-for-move, which makes it the simpler drop-in replacement.
The Frame–Stewart problem (four pegs)
The standard Tower of Hanoi uses three pegs. Add a fourth peg and the optimal move count is no longer 2^N − 1 — it is given by the Frame–Stewart algorithm, which splits the stack into a top group moved via all four pegs and a bottom group moved via the remaining three. The optimality of Frame–Stewart's recurrence was proven for the four-peg case in 2014 (Wikipedia: Tower of Hanoi — Frame–Stewart algorithm). For 10 disks, three-peg Hanoi needs 1,023 moves; four-peg Frame–Stewart needs 49.
The 64-disk prophecy
Suppose the priests move one disk per second, continuously. Completing 2^64 − 1 moves — 18,446,744,073,709,551,615 moves — would take approximately 585 billion years. (The Wikipedia entry on the Tower of Hanoi gives the standard formulation.)
The Milky Way is roughly 13.6 billion years old. Earth is roughly 4.54 billion years old. The prophecy is not on a tight schedule.
What each part of the solution signals about seniority
For hiring leads building a rubric, the four decision points below are where differentiation shows up:
- Base case precision. A junior candidate often starts with
N == 0. Stronger candidates pickN == 1because it maps to a concrete move. Either works, but the reasoning they give for the choice separates mechanical recall from understanding. - Argument ordering in the recursive call. The non-trivial part of this problem is that
auxandtoswap roles between the two recursive calls. Candidates who derive this correctly on the first try — rather than guess-and-check — are usually comfortable with recursion generally. - Articulating the invariant. "Before the big-disk move, all smaller disks are off the source and destination pegs" is the one-sentence invariant. Senior candidates volunteer it; others only confirm it when asked.
- Discussing iterative vs. recursive trade-offs. Candidates who can articulate both approaches — and name a concrete scenario where each is preferable — show stronger problem-solving signal than those who can only recite the recursive form.
For adjacent problem types that pair well with Tower of Hanoi in a leveling rubric, see HackerEarth's writeups on the top 7 algorithms and data structures every programmer should know and 7 steps to improve your data structure and algorithm skills.
FAQs
How many moves to solve Tower of Hanoi with 4 disks? Fifteen. Plugging N = 4 into 2^N − 1 gives 2^4 − 1 = 15. The 15 breaks down as 7 (move disks 1–3 off) + 1 (move disk 4) + 7 (move disks 1–3 back on top).
How can I solve Tower of Hanoi recursion on CSES or LeetCode?
Judge problems tagged "Tower of Hanoi" usually ask you to output the move sequence, not just the count. The recursive template above already prints each move as it executes — the only adjustments are matching the judge's exact output format (peg labels, spacing) and reading disk count from stdin. If the problem asks for the k-th move only, there is a closed-form solution based on the binary representation of k that avoids simulating all 2^N − 1 moves.
Is Tower of Hanoi a strong interview question in 2026, or is it overexposed? It is overexposed as a "produce the code" question — most candidates have seen it. It remains useful as a discussion question: ask the candidate to walk through their base-case choice, defend it, and extend to the iterative version. That reframes a memorized answer into a calibration conversation.
If a candidate solves Tower of Hanoi quickly, what should the follow-up be? Ask them to compute the k-th move without simulating the first k−1 (there is a closed-form answer involving the binary expansion of k), or ask them to adapt the algorithm to four pegs — the Frame–Stewart problem. Both extensions separate candidates who memorized the three-peg case from candidates who understand the structure.
Can Tower of Hanoi be solved with dynamic programming? Not usefully. The classic puzzle has no overlapping subproblems in a sense DP would exploit — each (N−1) subproblem is solved exactly twice regardless of memoization, and the total work is already 2^N − 1. Some variants of the puzzle framing (stacking disks under radius-and-height constraints, for example) reduce to the Longest Increasing Subsequence and are solved with DP. Those are distinct problems that borrow the name.
Does performance on Tower of Hanoi predict on-the-job recursion skill? Partially. It is a good screen for whether a candidate can decompose a problem into same-shape subproblems, which transfers to tree traversals, divide-and-conquer, and parser design. It is a weaker predictor of iterative or state-machine thinking, which is why pairing it with an iterative follow-up gives a more balanced signal.
For hiring teams: If you are calibrating a recursion rubric and want to see how candidates handle decomposition, base-case reasoning, and complexity analysis in a timed setting, HackerEarth Assessments lets you build role-aligned coding tests with recursion problems in the same family as Tower of Hanoi — including variants that surface the iterative-vs-recursive trade-off.
Estimated read time: 7 minutes
