Java Reference
In-Depth Information
the recursive method
countDown
just given. First we replace the
if
statement with a
while
statement.
Then, instead of the recursive call, we assign its argument
integer - 1
to the method's formal param-
eter
integer
. Doing so gives us the following iterative version of the method:
public static void
countDown(
int
integer)
{
while
(integer
>
= 1)
{
System.out.println(integer);
integer = integer - 1;
}
// end while
}
// end countDown
This method is essentially the same as the iterative method given in Segment 7.7.
Because converting tail recursion to iteration is often uncomplicated, some languages other
than Java automatically convert tail-recursive methods to iterative methods to save the overhead
involved with recursion. Most of this overhead involves memory, not time. If you need to save
space, you should consider replacing tail recursion with iteration.
7.43
Example.
Let's replace the tail recursion in the second version of the algorithm
solveTowers
given
in Segment 7.31:
Algorithm
solveTowers(numberOfDisks, startPole, tempPole, endPole)
if (numberOfDisks > 0)
{
solveTowers(numberOfDisks - 1, startPole, endPole, tempPole)
Move disk from
startPole
to
endPole
solveTowers(numberOfDisks - 1, tempPole, startPole, endPole)
}
This algorithm contains two recursive calls. The second one is tail recursive, since it is the algorithm's last
action. Thus, we could try replacing the second recursive call with appropriate assignment statements and
use a loop to repeat the method's logic, including the first recursive call, as follows:
Algorithm
solveTowers(numberOfDisks, startPole, tempPole, endPole)
while
(numberOfDisks > 0)
{
solveTowers(numberOfDisks - 1, startPole, endPole, tempPole)
Move disk from
startPole
to
endPole
numberOfDisks = numberOfDisks - 1
startPole = tempPole
tempPole = startPole
endPole = endPole
}
This isn't quite right, however. Obviously, assigning
endPole
to itself is superfluous.
Assigning
tempPole
to
startPole
and then assigning
startPole
to
tempPole
destroys
startPole
but leaves
tempPole
unchanged. What we need to do is exchange
tempPole
and
startPole
. Let's
look at what is really happening here.
The only instruction that actually moves disks is
Move disk from
startPole
to
endPole
. This
instruction moves the largest disk that is not already on
endPole
. The disk to be moved is at the bot-
tom of a pole, so any disks that are on top of it need to be moved first. Those disks are moved by the
first recursive call. If we want to omit the second recursive call, what would we need to do instead
before repeating the first recursive call? We must make sure that
startPole
contains the disks that
have not been moved to
endPole
. Those disks are on
tempPole
as a result of the first recursive call.
Thus, we need to exchange the contents of
tempPole
and
startPole
.
