The Tower of Hanoi
Move a tower of disks from peg A to peg C, one disk at a time, never a bigger disk on a smaller one. A recursive plan solves it for any number of disks: watch the calls and the moves, and find the pattern 2ⁿ − 1.
Core concept
To move n disks, move the top n − 1 out of the way, move the biggest, then move the n − 1 back on top; the same plan solves the smaller towers, so the moves double and add one each time: 2ⁿ − 1
Topic: Functions and recursion
The Tower of Hanoi is a puzzle with three pegs and a pile of disks, each smaller than the one below it. The disks must move from peg A to peg C, one at a time, and a bigger disk may never sit on a smaller one. It looks hard, but recursion makes it simple. To move a tower of n disks from A to C: first move the top n − 1 disks to the spare peg B (a smaller tower, solved the same way), then move the biggest disk to C, then move the n − 1 disks from B onto it. A tower of one disk is the base case: just move it. Each extra disk means solving the smaller tower twice and making one more move, so the moves are 1, 3, 7, 15, 31: always 2ⁿ − 1.
What you will learn
- Describe the recursive plan for the Tower of Hanoi.
- Find the base case of a recursive function.
- Explain why n disks take 2ⁿ − 1 moves.
- Predict how fast the moves grow as disks are added.
Before you start
- Know what a function is, and that a function can call itself (recursion).
Materials
- Three coins of different sizes and three marked spots, to try it by hand
Equipment
- None
Procedure
- Solve the tower with 3 disks and count the moves.
- Solve it with 4 disks.
- Step through a small tower and watch the calls.
- Answer the practice challenges.