Recursion - Advanced Topics in Java: Core Concepts in Data Structures - page 148

A B C

Figure 5-2. After four disks have been moved from A to C

We can now move the fifth disk from A to B , as shown in Figure 5-3 .

A B C

Figure 5-3. The fifth disk is placed on B

It remains only to transfer the four disks from C to B using A , which we assume we know how to do. The job is
completed as shown in Figure 5-4 .

A B C

Figure 5-4. After the four disks have been moved from C to B

We have thus reduced the problem of transferring five disks to a problem of transferring four disks from one pin
to another. This, in turn, can be reduced to a problem of moving three disks from one pin to another, and this can be
reduced to two and then to one, which we know how to do. The recursive solution for n disks is as follows:

1. Transfer n - 1 disks from A to C using B.

2. Move n th disk from A to B.

3. Transfer n - 1 disks from C to B using A.

Of course, we can use this same solution for transferring n - 1 disks.
The following function transfers n disks from startPin to endPin using workPin :

public static void hanoi(int n, char startPin, char endPin, char workPin) {
if (n > 0) {
hanoi(n - 1, startPin, workPin, endPin);
System.out.printf("Move disk from %c to %c\n", startPin, endPin);
hanoi(n - 1, workPin, endPin, startPin);
}
}