Recursion - Data Structures and Abstractions with Java - page 181

Using a Stack Instead of Recursion

7.45

One way to replace recursion with iteration is to simulate the program stack. In fact, we can imple-
ment a recursive algorithm by using a stack instead of recursion. As an example of converting a
recursive method to an iterative one, we will consider the method displayArray , as given in
Segment 7.18. For this demonstration, we will define displayArray as a nonstatic method in a
class that has an array as a data field. With these changes, the method appears as follows:
public void displayArray( int first, int last)
{

if (first == last)
System.out.println(array[first] + " ");
else
{

int mid = first + (last - first) / 2; // improved calculation of
// midpoint

displayArray(first, mid);
displayArray(mid + 1, last);
} // end if
} // end displayArray

7.46

We can replace the recursive method displayArray given in the previous segment with an itera-
tive version by using a stack that mimics the program stack. To do so, we create a stack that is
local to the method. We push objects onto this stack that are like the activation records described in
Segment 7.10. An activation record in Java's program stack contains the method's arguments, local
variables, and a reference to the current instruction. Since both recursive calls to displayArray are
consecutive, there is no need for our activation records to distinguish between them by storing a repre-
sentation of the program counter in the record. This simplification is not true in general, however.
To represent a record, we define a class that, in this case, has data fields for the method's argu-
ments first and last . The following simple class is sufficient if we make it internal to our class
containing displayArray :
private class Record
{

private int first, last;
private Record( int firstIndex, int lastIndex)
{

first = firstIndex;
last = lastIndex;
} // end constructor
} // end Record

7.47

In general, when a method begins execution, it pushes an activation record onto a program stack. At its
return, a record is popped from this stack. We want an iterative displayArray to maintain its own stack.
When the method begins execution, it should push a record onto this stack. Each recursive call should do
likewise. As long as the stack is not empty, the method should remove a record from the stack and act
according to the contents of the record. The method ends its execution when the stack becomes empty.
Here is an iterative version of displayArray that uses a stack as we just described:
private void displayArray( int first, int last)
{

boolean done = false ;
StackInterface<Record> programStack = new LinkedStack<Record>();
programStack.push( new Record(first, last));
while (!done && !programStack.isEmpty())
{

Record topRecord = programStack.pop();
first = topRecord.first;
last = topRecord.last;