Java Reference
In-Depth Information
7.31
Before we write some pseudocode to describe the algorithm, we need to identify a base case. If
only one disk is on pole 1, we can move it directly to pole 3 without using recursion. With this as
the base case, the algorithm is as follows:
Algorithm to move
numberOfDisks
disks from
startPole
to
endPole
using
tempPole
as a spare according to the rules of the Towers of Hanoi problem
if
(numberOfDisks == 1)
Move disk from
startPole
to
endPole
else
{
Move all but the bottom disk from
startPole
to
tempPole
Move disk from
startPole
to
endPole
Move all disks from
tempPole
to
endPole
}
At this point, we can develop the algorithm further by writing
Algorithm
solveTowers(numberOfDisks, startPole, tempPole, endPole)
if
(numberOfDisks == 1)
Move disk from
startPole
to
endPole
else
{
solveTowers(numberOfDisks - 1, startPole, endPole, tempPole)
Move disk from
startPole
to
endPole
solveTowers(numberOfDisks - 1, tempPole, startPole, endPole)
}
If we choose zero disks as the base case instead of one disk, we can simplify the algorithm a
bit, as follows:
Algorithm
solveTowers(numberOfDisks, startPole, tempPole, endPole)
// Version 2
if
(numberOfDisks > 0)
{
solveTowers(numberOfDisks - 1, startPole, endPole, tempPole)
Move disk from
startPole
to
endPole
solveTowers(numberOfDisks - 1, tempPole, startPole, endPole)
}
Although somewhat easier to write, the second version of the algorithm executes many more recur-
sive calls. Both versions, however, make the same moves.
Question 10
For two disks, how many recursive calls are made by each version of the algo-
rithm just given?
Your knowledge of recursion should convince you that both forms of the algorithm are correct.
Recursion has enabled us to solve a problem that appeared to be difficult. But is this algorithm effi-
cient? Could we do better if we used iteration?
7.32
Efficiency.
Let's look at the efficiency of our algorithm. How many moves occur when we begin
with
n
disks? Let
m
(
n
) denote the number of moves that
solveTowers
needs to solve the problem
for
n
disks. Clearly,
m
(1)
=
1
