RECURSION - Introduction to Java Programming: Comprehensive Version - page 720

Note
The Tower of Hanoi is a classic computer-science problem, to which many websites are
devoted. One of them worth looking at is www.cut-the-knot.com/recurrence/hanoi.shtml .

In the case of three disks, you can find the solution manually. For a larger number of
disks, however—even for four—the problem is quite complex. Fortunately, the problem has
an inherently recursive nature, which leads to a straightforward recursive solution.
The base case for the problem is n = 1 . If n == 1 , you could simply move the disk from A
to B. When n > 1 , you could split the original problem into the following three subproblems
and solve them sequentially.

1. Move the first n - 1 disks from A to C recursively with the assistance of tower B, as
shown in Step 1 in Figure 18.7.

2. Move disk n from A to B, as shown in Step 2 in Figure 18.7.

3. Move n - 1 disks from C to B recursively with the assistance of tower A, as shown in
Step 3 in Figure 18.7.

0 2

n - 1 disks n - 1 disks

.

.

A A B

Step 2: Move disk n fromAtoB

B
Original position

C C

1

3

n - 1 disks

n - 1 disks

.

.

A B
Step 1: Move the first n - 1 disks from
A to C recursively

C A B

Step 3: Move n - 1 disks from
C to B recursively

C

F IGURE 18.7

The Tower of Hanoi problem can be decomposed into three subproblems.

The following method moves n disks from the fromTower to the toTower with the assis-
tance of the auxTower :

void moveDisks( int n, char fromTower, char toTower, char auxTower)

The algorithm for the method can be described as:

if (n == 1) // Stopping condition
Move disk 1 from the fromTower to the toTower;
else {
moveDisks(n - 1, fromTower, auxTower, toTower);
Move disk n from the fromTower to the toTower;
moveDisks(n - 1, auxTower, toTower, fromTower);
}