Overview
The Tower of Hanoi is a classic puzzle with three pegs and a stack of disks of different sizes. All disks start on one peg in size order, and the goal is to move the whole stack to another peg while never placing a larger disk on a smaller one and moving only one disk at a time.
It is the purest illustration of recursion: to move n disks from a source peg to a target peg, you first move the top n−1 disks to the spare peg, move the largest disk across, then move those n−1 disks back on top. Each subproblem is a smaller copy of the original, which makes the recursive solution both short and elegant.
How Tower of Hanoi works
- State the goal as: move n disks from the source peg to the target peg using the third peg as an auxiliary.
- Base case: if there is a single disk, move it directly from source to target — no recursion needed.
- Recursively move the top n−1 disks from the source to the auxiliary peg, keeping the largest disk untouched at the bottom.
- Move the single largest disk from the source directly to the target peg.
- Recursively move the n−1 disks from the auxiliary peg onto the target, completing the stack in order.
When to use it
- Teaching recursion, the divide-and-conquer mindset, and how a problem reduces to smaller copies of itself.
- Illustrating the call stack and recursion depth, since the stack grows to depth n.
- A benchmark for comparing recursive and equivalent iterative implementations.
- Modelling ordered transfer tasks where constraints forbid certain intermediate configurations.
Complexity analysis
Solving n disks requires exactly 2^n − 1 moves, which is provably optimal, so the running time is O(2^n) — it doubles with each additional disk. The recursion reaches depth n, giving O(n) space on the call stack. Unlike search-based backtracking, no branch is ever abandoned: every recursive call contributes to the final answer.
Frequently asked questions
Why does it always take 2^n − 1 moves?
Let T(n) be the moves needed for n disks. Each solution moves n−1 disks twice plus the largest disk once, so T(n) = 2·T(n−1) + 1 with T(1) = 1, which solves to exactly 2^n − 1. This count is optimal — no valid strategy can do fewer moves.
Is Tower of Hanoi backtracking or plain recursion?
It is pure recursion, not backtracking. There are no dead ends to undo: every move is part of the optimal solution, so the algorithm never has to abandon a branch and retry a different choice.
Can it be solved without recursion?
Yes. There is an iterative version driven by a simple move pattern (and even a binary-counter interpretation), but the recursive formulation is the clearest expression of the underlying divide-and-conquer idea.