Java Reference
In-Depth Information
you might want to eliminate the overhead imposed by the recursive function calls.
In some cases, such as the factorial function of Section 2.5, recursion can easily be
replaced by iteration.
Example4.2
As a simple example of replacing recursion with a stack,
consider the following non-recursive version of the factorial function.
/
**
@returnn!
*
/
staticlongfact(intn){
//Tofitn!inalongvariable,requiren<21
assert(n>=0)&&(n<=20):"noutofrange";
//Makeastackjustbigenough
Stack<Integer>S=newAStack<Integer>(n);
while(n>1)S.push(n--);
longresult=1;
while(S.length()>0)
result=result
*
S.pop();
returnresult;
}
Here, we simply push successively smaller values of n onto the stack un-
til the base case is reached, then repeatedly pop off the stored values and
multiply them into the result.
An iterative form of the factorial function is both simpler and faster than the
version shown in Example 4.2. But it is not always possible to replace recursion
with iteration. Recursion, or some imitation of it, is necessary when implementing
algorithms that require multiple branching such as in the Towers of Hanoi alg-
orithm, or when traversing a binary tree. The Mergesort and Quicksort algorithms
of Chapter 7 are also examples in which recursion is required. Fortunately, it is al-
ways possible to imitate recursion with a stack. Let us now turn to a non-recursive
version of the Towers of Hanoi function, which cannot be done iteratively.
Example4.3
The
TOH
function shown in Figure 2.2 makes two recursive
calls: one to move n 1 rings off the bottom ring, and another to move
these n 1 rings back to the goal pole. We can eliminate the recursion by
using a stack to store a representation of the three operations that
TOH
must
perform: two recursive calls and a move operation. To do so, we must first
come up with a representation of the various operations, implemented as a
class whose objects will be stored on the stack.
Figure 4.23 shows such a class. We first define an enumerated type
called
TOHop
, with two values MOVE and TOH, to indicate calls to the
move
function and recursive calls to
TOH
, respectively. Class
TOHobj
stores five values: an operation field (indicating either a move or a new
TOH operation), the number of rings, and the three poles. Note that the
