The Tower of Hanoi is the classic puzzle that makes recursion click.
Move all disks from peg A to peg C — only one disk at a time, never a bigger disk on a smaller one.
Watch the call stack build and unwind as the computer solves it, or try it yourself.
Try:
Disks:
Minimum moves: 7
Your moves: 0
A
B
C
Why this move?
Press Solve or Step → to begin.
Click a peg to pick up the top disk, then click another peg to place it.
🎉 Solved in 0 moves! Minimum was 0.
📞 Call Stack (live)
— stack is empty —
📄 Recursive Algorithm
def hanoi(n, src, aux, dst):if n == 0: returnhanoi(n-1, src, dst, aux)move disk n: src → dsthanoi(n-1, aux, src, dst)
Total moves = 2ⁿ − 1
Each call spawns 2 more (like a tree).
Base case: n = 0, do nothing.
How to use
Pick the number of disks (start with 3 to see the pattern clearly).
In Watch it Solve mode, press Solve to watch the computer work through it, or use Step → to advance one move at a time.
Watch the Call Stack — each box is one active function call. The highlighted line in the pseudocode shows where the computer is right now.
Switch to Play Yourself and try to solve it in the minimum number of moves. Use the Hint button if you're stuck.
Try 4 disks after mastering 3. Notice the pattern: the same solution repeats itself, smaller each time — that's recursion.
Frequently Asked Questions
What is recursion?
Recursion is when a function calls itself to solve a smaller version of the same problem. It keeps calling itself until it hits the base case (n = 0), then all the calls return one by one.
Why does it take 2ⁿ − 1 moves?
To move n disks you must first move n−1 disks out of the way, make 1 move for the biggest disk, then move n−1 disks again. So T(n) = 2·T(n−1) + 1, which solves to 2ⁿ − 1.
What is the call stack?
Every time a function is called, the computer saves its state on a stack. When that call finishes, it pops off the stack and the previous call resumes. Deep recursion = tall stack.
What is the base case and why does it matter?
The base case (n = 0, do nothing) is what stops the recursion. Without it the function would call itself forever and the program would crash with a stack overflow.
Is there a non-recursive solution?
Yes — you can use an iterative approach with an explicit stack, but the recursive version is far more elegant and is the best example of how recursion "thinks" for students learning the concept.
Did you know?
The Tower of Hanoi was invented by French mathematician Édouard Lucas in 1883.
With 64 disks (the legend involves 64 golden disks), the solution takes 2⁶⁴ − 1 ≈ 18.4 quintillion moves. At one move per second that's 585 billion years.
The sequence of which peg to move from at each step follows a simple pattern: alternate between the smallest disk and the only legal move that doesn't involve the smallest disk.