Java Reference
In-Depth Information
16
/** The method for finding the solution to move n disks
17
from fromTower to toTower with auxTower */
18
public static void
19 {
20
if
(n ==
1
)
// Stopping condition
21 System.out.println(
"Move disk "
+ n +
" from "
+
22 fromTower +
" to "
+ toTower);
23
else
{
24 ;
25 System.out.println(
"Move disk "
+ n +
" from "
+
26 fromTower +
" to "
+ toTower);
27
moveDisks(
int
n,
char
fromTower,
char
toTower,
char
auxTower)
base case
moveDisks(n -
1
, fromTower, auxTower, toTower)
recursion
moveDisks(n -
1
, auxTower, toTower, fromTower)
;
recursion
28 }
29 }
30 }
Enter number of disks:
The moves are:
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
Move disk 4 from A to B
Move disk 1 from C to B
Move disk 2 from C to A
Move disk 1 from B to A
Move disk 3 from C to B
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
4
This problem is inherently recursive. Using recursion makes it possible to find a natural, sim-
ple solution. It would be difficult to solve the problem without using recursion.
Consider tracing the program for
n = 3
. The successive recursive calls are shown in
Figure 20.8. As you can see, writing the program is easier than tracing the recursive calls. The
moveDisks(3,'A','B','C')
moveDisks(2,'A','C','B')
move disk 3 from A to B
moveDisks(2,'C','B','A')
moveDisks(2,'A','C','B')
moveDisks(2,'C','B','A')
moveDisks(1,'A','B','C')
move disk 2 from A to C
moveDisks(1,'B','C','A')
moveDisks(1,'C','A','B')
move disk 2 from C to B
moveDisks(1,'A','B','C')
moveDisks(1,'A','B','C')
move disk 1 from A to B
moveDisks(1,'B','C','A')
move disk 1 from B to C
moveDisks(1,'C','A','B')
move disk 1 from C to A
moveDisks(1,'A','B','C')
move disk 1 from A to B
F
IGURE
20.8
Invoking
moveDisks(3, 'A', 'B', 'C')
spawns calls to
moveDisks
recursively.
