The Tower of Hanoi

Move the stack

An interactive lesson with 6 steps, about 5 minutes: you predict, drag and solve, with instant feedback on every answer. It runs in your browser and needs JavaScript.

What you’ll learn

• Recursion: solve a problem using solutions to smaller versions.
• Tower of Hanoi: $M(n) = 2M(n-1) + 1 = 2^n - 1$.
• 64 discs would take 585 billion years.

Steps

1. The puzzle
2. Four discs
3. Watch it solve
4. The smallest disc
5. Ten discs
6. The legend