A First Taste of Algorithms

Chapter 3: The Procedure That Calls Itself

✦ ✦ ✦

In which a puzzle is solved by handing it to a smaller you

Three pegs, a rule, and a tower

The puzzle: three pegs stand in a row. On the left peg sits a tower of disks, largest on the bottom, smallest on top. Move the whole tower to the right peg, under two laws: move one disk at a time, and never place a larger disk on a smaller one.

Get three coins of different sizes and play — this chapter is useless watched and easy played.

One disk: move it. One move.

Two disks: the small one is in the way, so park it on the middle peg, move the big one to the right, drop the small one back on top. Three moves.

Three disks. Fumble for a minute — everyone does — and then catch yourself doing something remarkable. To free the big disk, you must first move the two-disk tower above it out of the way, onto the middle peg. But you just learned how to move a two-disk tower — you do it again, aiming at the middle. Then the big disk crosses. Then you move the two-disk tower once more, middle to right. Done in 3 + 1 + 3 = 7 moves, and the three-disk solution turned out to contain the two-disk solution, twice, as a part.

That observation, taken seriously, solves the puzzle for every tower at once. To move n disks from here to there:

move the top n − 1 disks to the spare peg — somehow; carry disk n across; move the n − 1 disks from the spare onto it — somehow.

And the scandal is what fills in “somehow”: the same instructions, for a smaller tower. The procedure delegates its hard part to itself. A four-disk tower asks the three-disk procedure for help; the three-disk procedure asks the two-disk; the two asks the one; and the one-disk case needs no help at all — pick it up, put it down.

This is recursion: a procedure defined partly in terms of itself, on smaller cases. It is the deepest idea in this book, and your first reaction to it should be suspicion.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses