Java Reference
In-Depth Information
If we try to find an iterative solution, we'll likely find ourselves hopelessly “knotted
up” in managing the disks. Instead, attacking this problem recursively quickly yields a
solution. Moving
n
disks can be viewed in terms of moving only
n
- 1 disks (hence the
recursion) as follows:
1.
Move
n
- 1 disks from peg 1 to peg 2, using peg 3 as a temporary holding area.
2.
Move the last disk (the largest) from peg 1 to peg 3.
3.
Move
n
- 1 disks from peg 2 to peg 3, using peg 1 as a temporary holding area.
The process ends when the last task involves moving
n
= 1 disk (i.e., the base case).
This task is accomplished by moving the disk, without using a temporary holding area.
In Fig. 18.11, method
solveTowers
(lines 6-25) solves the Towers of Hanoi, given
the total number of disks (in this case
3
), the starting peg, the ending peg, and the tempo-
rary holding peg as parameters. The base case (lines 10-14) occurs when only one disk
needs to be moved from the starting peg to the ending peg. In the recursion step (lines 18-
24), line 18 moves
disks - 1
disks from the first peg (
sourcePeg
) to the temporary
holding peg (
tempPeg
). When all but one of the disks have been moved to the temporary
peg, line 21 moves the largest disk from the start peg to the destination peg. Line 24 fin-
ishes the rest of the moves by calling the method
solveTowers
to recursively move
disks -
1
disks from the temporary peg (
tempPeg
) to the destination peg (
destinationPeg
), this
time using the first peg (
sourcePeg
) as the temporary peg. Line 35 in
main
calls the recur-
sive
solveTowers
method, which outputs the steps to the command prompt.
1
// Fig. 18.11: TowersOfHanoi.java
2
// Towers of Hanoi solution with a recursive method.
3
public
class
TowersOfHanoi
4
{
5
// recursively move disks between towers
6
public
static void
solveTowers(
int
disks,
int
sourcePeg,
int
destinationPeg,
int
tempPeg)
7
8
{
9
// base case -- only one disk to move
10
if
(disks ==
1
)
11
{
12
System.out.printf(
"%n%d --> %d"
, sourcePeg, destinationPeg);
13
return
;
14
}
15
16
// recursion step -- move (disk - 1) disks from sourcePeg
17
// to tempPeg using destinationPeg
18
solveTowers(disks -
1
, sourcePeg, tempPeg, destinationPeg);
19
20
// move last disk from sourcePeg to destinationPeg
21
System.out.printf(
"%n%d --> %d"
, sourcePeg, destinationPeg);
22
23
// move (disks - 1) disks from tempPeg to destinationPeg
24
solveTowers(disks -
1
, tempPeg, destinationPeg, sourcePeg);
25
}
26
Fig. 18.11
|
Towers of Hanoi solution with a recursive method. (Part 1 of 2.)
