Java Reference
In-Depth Information
Note:
Invented in the late 1800s, the Towers of Hanoi problem was accompanied by this
legend. A group of monks was said to have begun moving 64 disks from one tower to
another. When they finish, the world will end. When you finish reading this section, you will
realize that the monks—or their successors—could not have finished yet. By the time they
do, it is quite plausible that the disks, if not the world, will have worn out!
7.30
A recursive algorithm solves a problem by solving one or more smaller problems of the
same type. The problem size here is simply the number of disks. So imagine that the first
pole has four disks, as in Figure 7-9a, and that I ask you to solve the problem. Eventually,
you will need to move the bottom disk, but first you need to move the three disks on top of
it. Ask a friend to move these three disks—a smaller problem—according to our rules, but
make pole 2 the destination. Allow your friend to use pole 3 as a spare. Figure 7-9b shows
the final result of your friend's work.
When your friend tells you that the task is complete, you move the one disk left on pole 1 to
pole 3. Moving one disk is a simple task. You don't need help—or recursion—to do it. This disk
is the largest one, so it cannot rest on top of any other disk. Thus, pole 3 must be empty before
this move. After the move, the largest disk will be first on pole 3. Figure 7-9c shows the result of
your work.
Now ask a friend to move the three disks on pole 2 to pole 3, adhering to the rules. Allow your
friend to use pole 1 as a spare. When your friend tells you that the task is complete, you can tell me
that your task is complete as well. Figure 7-9d shows the final results.
FIGURE 7-9
The smaller problems in a recursive solution for four disks
(a)
1
2
3
(b)
3
1
2
(c)
2
3
1
(d)
2
3
1
