Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
The Tower of Hanoi
In the aforementioned movie “Battle for the Planet of the Apes,” the apes at the beginning of the story are given a test: solve a puzzle involving three poles. The first pole has several rings on it, each ring smaller than the one below it. The other two poles are empty at the start. The challenge is to move all the rings to the third pole.
)
The apes have to follow two rules of movement:
- An ape can move the top ring—and only the top ring—to any of the other two poles and drop it on the existing stack of rings that are already there, if any. (Once that ring is moved, the ape can then move the ring below it.)
- An ape can never place a bigger ring on top of a smaller ring.
One of the apes—the one that eventually takes over the world—gets to be very good at this puzzle.
Recursion in some form (either explicit or simulated) should be used to solve the puzzle for the reason I gave earlier: The correct solution involves contexts inside of contexts inside of contexts. For simple movement (move one ring from pole 1 to pole 2), the solution is trivial. The general solution is as follows.
To move N rings from a source pole to a destination pole:
- Move N-1 rings from the source pole to the “other” pole—that is, the pole that is neither the source nor the final destination.
- Move one ring from the source pole to the destination pole.
- Move N-1 rings from the “other” pole to the destination pole.
Once you grasp this general strategy, the C++ code is easy enough to write:
solve_tower(int n, int source, int dest, int other) {
if (n <= 1)
cout << "Move from " << source << " to " << dest << ".";
else {
solve_tower(n-1, source, other, dest);
solve_tower(1, source, dest, other);
solve_tower(n-1, other, dest, source);
}
To move five rings from pole 1 to pole 3, you’d call:
solve_tower(5, 1, 3, 2); // Move 5 rings from pole 1 to 3;
// 2 is the other pole.
This is a perfect use of recursion because it is like the “Inception” scenario I described earlier. Each level of the puzzle depends on first solving the puzzle one level deeper (or “above” it using the stack pictures shown earlier). To know where you are and what you doing at any given moment, you must remember where you are within the complex stack of cases within cases—that is, in the dream within the dream. Recursion lets the program keep track all the contexts for you.
(Eventually, you wake up and find the puzzle completely solved, just as Leonardo DiCaprio eventually wakes up and finds that everything is perfect… or does he?)
Incidentally, just as you can use recursion to simulate iteration, you can do the converse. It is always possible to simulate recursion by using a user-created stack (like the ones you can create by using the Standard Template Library). Ultimately, what matters is that you use a last-in-first-out mechanism to keep track of the current context before “popping out” to the next level.