|
|
|
 |
|
|
|
Towers of Hanoi Iteratively
|
|
| |
Contributed by Roselyn Teukolsky
Ithaca High School
Ithaca, New York
There's something magical about recursion, because of all the bookkeeping needed to keep track of things.
Most people know the recursive solution to the Towers of Hanoi problem. But
there's also a wonderfully easy iterative solution that was discovered in 1980 by Peter Buneman and Leon Levy.
Assume that the n disks start on peg A and must end up on peg C, after using peg B as the spare peg.
1) Move the smallest disk from its current peg to the next peg in clockwise (or counter-clockwise -- just stick with the same direction) order.
2) Move any other disk.
The second step is not arbitrary. It turns out that there's only one such legal move.
This is how the solution works: go clockwise with the smallest disk, make a legal
move with another disk, go clockwise with the smallest disk, make a legal move with
another disk, and so on. Eventually n-1 disks will have magically been transferred to peg
B using peg C as the spare; then the largest disk goes to peg C; then those n-1 disks
eventually get to peg C using peg B as the spare.
When I teach this, I chat to the kids while simultaneously performing the solution
to the puzzle on Fisher Price stack toys. I don't immediately divulge that I'm using an
iterative solution. I tell the kids that I'm thinking recursively, keeping track as I go. This
impresses the heck out of them!
|
|
|
|
|
|
Course Home Pages