Below is an excerpt from one page of a course from which I'm teaching myself
Java online. There's one part
of this I haven't been able to understand.
You might need no more than the excerpt below, but you can find the full page here:
http://math.hws.edu/javanotes/c11/s1.html The following page has a nice little
applet that lets you play with the problem.
http://www.cut-the-knot.com/recurrence/hanoi.html The only part I don't quite get is how the change in order of the parameters to TowersOfHanoi() actually
accomplishes the needed disk movements. In other words, can you explain WHY this works: how the
interaction between the following three lines actually results in the proper moves?
TowersOfHanoi(int disks, int from, int to, int spare) TowersOfHanoi(disks-1, from, spare, to);
TowersOfHanoi(disks-1, spare, to, from);
The excerpt follows. Thanks.
******** begin excerpt ********
Next, we turn to a problem that is easy to solve with recursion but difficult to solve without it. This is a
standard example known as "The Towers of Hanoi". The problem involves a stack of various-sized disks, piled
up on a base in order of decreasing size. The object is to move the stack from one base to another, subject
to two rules: Only one disk can be moved at a time, and no disk can ever be placed on top of a smaller disk.
There is a third base that can be used as a "spare". The situation for a stack of ten disks is shown in the
top half of the following picture. The situation after a number of moves have been made is shown in the
bottom half of the picture. These pictures are from the applet at the end of Section 10.5, which displays an
animation of the step-by-step solution of the problem.
[pictures of stacks of disks were here]
The problem is to move ten disks from Stack 0 to Stack 1, subject to certain rules. Stack 2 can be used a
spare location. Can we reduce this to smaller problems of the same type, possibly generalizing the problem a
bit to make this possible? It seems natural to consider the size of the problem to be the number of disks to
be moved. If there are N disks in Stack 0, we know that we will eventually have to move the bottom disk from
Stack 0 to Stack 1. But before we can do that, according to the rules, the first N-1 disks must be on Stack
2. Once we've moved the N-th disk to Stack 1, we must move the other N-1 disks from Stack 2 to Stack 1 to
complete the solution. But moving N-1 disks is the same type of problem as moving N disks, except that it's
a smaller version of the problem. This is exactly what we need to do recursion! The problem has to be
generalized a bit, because the smaller problems involve moving disks from Stack 0 to Stack 2 or from Stack 2
to Stack 1, instead of from Stack 0 to Stack 1. In the recursive subroutine that solves the problem, the
stacks that serve as the source and destination of the disks have to be specified. It's also convenient to
specify the stack that is to be used as a spare, even though we could figure that out from the other two
parameters. The base case is when there is only one disk to be moved. The solution in this case is trivial:
Just move the disk in one step. Here is a version of the subroutine that will print out step-by-step
instructions for solving the problem:
void TowersOfHanoi(int disks, int from, int to, int spare) {
if (disks == 1) {
System.out.println("Move a disk from stack number " + from + " to stack number " + to); }
else{
TowersOfHanoi(disks-1, from, spare, to);
System.out.println("Move a disk from stack number " + from + " to stack number " + to);
TowersOfHanoi(disks-1, spare, to,from); }
}
This subroutine just expresses the natural recursive solution. The recursion works because each recursive
call involves a smaller number of disks, and the problem is trivial to solve in the base case, when there is
only one disk. To solve the "top level" problem of moving N disks from Stack 0 to Stack 1, it should be
called with the command TowersOfHanoi(N,0,1,2).
********** end excerpt ***********