Overview
The Tower of Hanoi was invented by French mathematician Édouard Lucas in 1883, wrapped in a legend about monks moving 64 golden disks. It is the purest illustration of recursion: the solution for n disks is built entirely from the solution for n−1.
You may move only the top disk of a peg and may never place a larger disk on a smaller one, yet the whole stack can always be relocated — and always in the same provably minimum number of moves.
How to solve Tower of Hanoi
- Think recursively: to move n disks from A to C, first get the top n−1 disks out of the way onto B.
- Move the single largest disk directly from A to C.
- Move the n−1 disks from B onto C, on top of the largest disk.
- Each of those n−1 sub-moves is the same puzzle one size smaller, all the way down to a single disk (the base case).
The key insight
Solving n disks requires exactly 2ⁿ − 1 moves, because T(n) = 2·T(n−1) + 1. Each extra disk doubles the work — a vivid demonstration of exponential growth from a trivially simple rule.
Variations & echoes
- It is the textbook example for teaching recursion and the call stack in programming courses.
- There is also an iterative solution driven by a simple 'smallest disk moves every other turn' rule.
- The legend's 64 disks would take 2⁶⁴ − 1 moves — over 580 billion years at one move per second.
Frequently asked questions
Why exactly 2ⁿ − 1 moves?
Because moving n disks means moving n−1 twice plus the biggest disk once: T(n) = 2·T(n−1) + 1 with T(1) = 1, which solves to 2ⁿ − 1.
Is this backtracking?
No — it's pure recursion. Every move is part of the optimal path, so nothing is ever undone.