TwiddleLab / Code / Recursion: Functions That Call Themselves

Towers of Hanoi

Lesson 6 of 11 · 7 min · Free, no account needed

What you will learn

• A recursive plan: to move n disks, move n - 1 out of the way, move the biggest, then move the n - 1 back on top.
• The two smaller moves are the same puzzle, so the function calls itself twice. The base case is 0 disks: do nothing.
• The moves double each time, plus one: 2^n - 1. 64 disks would take about 585 billion years at one move a second.

Start the lesson

How the lesson goes

1. Monks move 64 golden disks. When they finish, the world ends. Should we worry?

   Try 3 disks first. Move the tower from A to C: one disk at a time, never a bigger one on a smaller one.

2. One more disk. How many moves for 4?

   3 disks took 7 at best.

3. Think of the top 3 disks as one block.

   Get the block off the big disk, move the big disk to C, put the block back on top.

   The big disk can only move when everything above it is on the spare peg. Getting 3 disks there is the 3-disk puzzle (7 moves); then 1 move; then the 3-disk puzzle again (7 moves).

4. A recursive plan.

   To move n disks from A to C: move n - 1 disks from A to B, move the biggest from A to C, move n - 1 disks from B to C.

   Both smaller moves are the same puzzle with one disk fewer, so the function calls itself twice. That's a recursive plan.

   The base case: 0 disks, nothing to do. Moves: 2 x (moves for n - 1) + 1.

5. Beat the monk: 4 disks by hand.

   Par is 15. Use the plan: 3 out of the way, big one across, 3 back.

6. Write the plan as code.

   hanoi(n, a, b, c) moves n disks from a to b, using c as the spare. Make it print the 3 moves for 2 disks.

   hanoi(n - 1, a, c, b) clears the way onto the spare c. print moves the biggest disk. hanoi(n - 1, c, b, a) brings the smaller tower from the spare onto the target b.

7. Let your recursion play 5 disks.

   Your code prints every move. The pegs follow it.

8. How do the moves grow with the tower?

   Slide up to 10 disks.

9. The monks have 64 disks and make one move a second. How long?

   2^64 - 1 seconds. Estimate it in years, then Check. Within 3 times either way counts.

   2^64 - 1 is about 1.8 x 10^19 seconds. Divide by about 3.16 x 10^7 seconds in a year: about 5.8 x 10^11, or 585 billion years.

10. Speed round: where does the smallest disk go first?

    Towers of 1 to 6 disks, always from A to C. Tap the peg for the very first move.

Previous lesson: Remember Answers: Memoization · Next lesson: Drawing Fractals · Part of the course: Recursion: Functions That Call Themselves

Lessons are interactive and need JavaScript. Turn it on to play them.