294 CHAPTER 6 Recursion
number of comparisons to sort a specific array depends on how the data is arranged,
but it will be somewhere between the maximum and minimum values.
Eliminating Recursion
Some algorithms lend themselves to a recursive approach, some don’t. As we’ve seen,
the recursive and methods can be implemented more effi-
ciently using a simple loop. However, various divide-and-conquer algorithms, such as
mergesort, work very well as recursive routines.
Often an algorithm is easy to conceptualize as a recursive method, but in practice
the recursive approach proves to be inefficient. In such cases, it’s useful to transform
the recursive approach into a non-recursive approach. Such a transformation can
often make use of a stack.
Recursion and Stacks
There is a close relationship between recursion and stacks. In fact, most compilers
implement recursion by using stacks. As we noted, when a method is called, the
compiler pushes the arguments to the method and the return address (where control
will go when the method returns) on the stack, and then transfers control to the
method. When the method returns, it pops these values off the stack. The arguments
disappear, and control returns to the return address.
Simulating a Recursive Method
In this section we’ll demonstrate how any recursive solution can be transformed into
a stack-based solution. Remember the recursive method from the first
section in this chapter? Here it is again:
We’re going to break this algorithm down into its individual operations, making
each operation one in a statement. (You can perform a similar decompo-
sition using statements in C++ and some other languages, but Java doesn’t
support .)
The statement is enclosed in a method called . Each call to causes
one section within the to be executed. Calling repeatedly will
eventually execute all the code in the algorithm.
Eliminating Recursion 295
The method we just saw performs two kinds of operations. First, it carries
out the arithmetic necessary to compute triangular numbers. This involves checking
if is 1, and adding to the results of previous recursive calls. However,
also performs the operations necessary to manage the method itself, including trans-
fer of control, argument access, and the return address. These operations are not
visible by looking at the code; they’re built into all methods. Here, roughly speaking,
is what happens during a call to a method:
• When a method is called, its arguments and the return address are pushed
onto a stack.
• A method can access its arguments by peeking at the top of the stack.
• When a method is about to return, it peeks at the stack to obtain the return
address, and then pops both this address and its arguments off the stack and
discards them.
The program contains three classes: , , and
. The class encapsulates the return address and the method’s
argument, ; objects of this class are pushed onto the stack. The class is
similar to those in other chapters, except that it holds objects of class . The
class contains four methods: , , , and the
usual method for numerical input.
The routine asks the user for a number, calls the method to
calculate the triangular number corresponding to , and displays the result.
The method creates a object and initializes to 1. It then
settles into a loop, where it repeatedly calls . It won’t exit from the loop
until returns by reaching case 6, its exit point. The method is basi-
cally a large statement in which each corresponds to a section of code in
the original method. Listing 6.7 shows the program.
LISTING 6.7 The [Link] Program
296 CHAPTER 6 Recursion
LISTING 6.7 Continued
Eliminating Recursion 297
LISTING 6.7 Continued
298 CHAPTER 6 Recursion
LISTING 6.7 Continued
This program calculates triangular numbers, just as the program
(Listing 6.1) at the beginning of the chapter did. Here’s some sample output:
Eliminating Recursion 299
Figure 6.19 shows how the sections of code in each relate to the various parts of
the algorithm.
Case 1:
Initial call
simMeth() Simulated method
Case 2: Entry
Test Done
Not Done
Case 3: Call method
Case 4: Do calculation
Case 5:
Exit
Case 6:
Return
point
FIGURE 6.19 The cases and the step() method.
The program simulates a method, but it has no name in the listing because it isn’t a
real Java method. Let’s call this simulated method . The initial call to
(at case 1) pushes the value entered by the user and a return value of 6
onto the stack and moves to the entry point of (case 2).
At its entry (case 2), tests whether its argument is 1. It accesses the argu-
ment by peeking at the top of the stack. If the argument is 1, this is the base case
300 CHAPTER 6 Recursion
and control goes to ’s exit (case 5). If not, it calls itself recursively (case 3).
This recursive call consists of pushing and a return address of 4 onto the stack,
and going to the method entry at case 2.
On the return from the recursive call, adds its argument to the value
returned from the call. Finally, it exits (case 5). When it exits, it pops the last
object off the stack; this information is no longer needed.
The return address given in the initial call was 6, so case 6 is the place where control
goes when the method returns. This code returns to let the loop in
know that the loop is over.
Note that in this description of ’s operation we use terms like argument,
recursive call, and return address to mean simulations of these features, not the normal
Java versions.
If you inserted some output statements in each to see what was doing,
you could arrange for output like this:
The case number shows what section of code is being executed. The contents of the
stack (consisting of objects containing followed by a return address) are also
shown. The method is entered four times (case 2) and returns four times
(case 5). Only when it starts returning does begin to accumulate the results
of the calculations.
Eliminating Recursion 301
What Does This Prove?
In (Listing 6.7) we have a program that more or less systemati-
cally transforms a program that uses recursion into a program that uses a stack. This
suggests that such a transformation is possible for any program that uses recursion,
and in fact this is the case.
With some additional work, you can systematically refine the code we show here,
simplifying it and even eliminating the statement entirely to make the code
more efficient.
In practice, however, it’s usually more practical to rethink the algorithm from the
beginning, using a stack-based approach instead of a recursive approach. Listing 6.8
shows what happens when we do that with the method.
LISTING 6.8 The [Link] Program
302 CHAPTER 6 Recursion
LISTING 6.8 Continued
Some Interesting Recursive Applications 303
LISTING 6.8 Continued
Here two short loops in the method substitute for the entire
method of the program. Of course, in this program you
can see by inspection that you can eliminate the stack entirely and use a simple
loop. However, in more complicated algorithms the stack must remain.
Often you’ll need to experiment to see whether a recursive method, a stack-based
approach, or a simple loop is the most efficient (or practical) way to handle a
particular situation.
Some Interesting Recursive Applications
Let’s look briefly at some other situations in which recursion is useful. You will see
from the diversity of these examples that recursion can pop up in unexpected places.
We’ll examine three problems: raising a number to a power, fitting items into a
knapsack, and choosing members of a mountain-climbing team. We’ll explain the
concepts and leave the implementations as exercises.
Raising a Number to a Power
The more sophisticated pocket calculators allow you to raise a number to an arbi-
trary power. They usually have a key labeled something like x^y, where the circum-
flex indicates that x is raised to the y power. How would you do this calculation if
your calculator lacked this key? You might assume you would need to multiply x by
itself y times. That is, if x was 2 and y was 8 (28), you would carry out the arithmetic
for 2*2*2*2*2*2*2*2. However, for large values of y, this approach might prove
tedious. Is there a quicker way?
One solution is to rearrange the problem so you multiply by multiples of 2 whenever
possible, instead of by 2. Take 28 as an example. Eventually, we must involve eight 2s
in the multiplication process. Let’s say we start with 2*2=4. We’ve used up two of the