Recursion Removal
The first question is whether every recursive method had an equivalent iterative
method. This is true but it is hardly obvious. For any recursive method, we can remove
the recursion by writing the code that essentially does what the computer does. The
computer uses a stack to keep track of the calls and returns. When you call a method,
the following items are pushed onto the calling stack.
1. The values of the local variables.
2. The values of any parameter variables that are passed "by value". In Java, these are
the parameters of the built-in types.
3. The location of the call -- actually the address of the next instruction to execute.
Then the arguments are passed into the parameters of the called method. Execution
then starts at the beginning of the called method. When a method ends and returns
back to the calling method, the following happens.
1. Pop the stack.
2. Restore the values of the local variables and the values of the parameters passed by
value.
3. Store the returned value, if any.
4. Continue execution starting at the popped location.
To convert a recursive method to a non-recursive one, we use a stack and manually
follow the spirit of the steps outlined above when we call and return from the method.
To illustrate this, consider the following recursive fibonacci function.
int fib( int n )
{
if (n == 0) return 0;
if (n == 1) return 1;
return fib( n-1 ) + fib( n-2 );
}
In order to be able to apply the call and return procedures. I'll rewrite this so that the
two recursive calls and the return all appear on separate lines. I'll also label the lines;
the labels are essentially the locations that are pushed onto the stack.
int fib( int n )
{
0: if (n == 0) return 0;
1: if (n == 1) return 1;
2: int P1 = fib( n-1 );
3: int P2 = fib( n-2 );
4: int retVal = P1 + P2;
5: // return procedure
}
The items that need to be pushed onto the stack are P1, P2, n, and the label that
indicates the location of the next line to execute (we can get away with not pushing
ret_val because it is not declared and used until after we return from both recursive
calls). To do this, we write a StackItem class which has four private data members for
storing these values. The needed functions are a constructor which sets the private
values according to the passed in arguments and getters for each of the values. For
conciseness of description, I'll denote a StackItem object as <P1,P2,N,l>.
Now we apply the call and return procedures to our modified method above. We
replace lines 2 and 3 with
2: [Link]( <P1, P2, n, 3> ); // stack vars. and location
n--; // set parameter to n-1
goto line 0; // goto start of method
3: [Link]( <P1, P2, n, 4> ); // stack vars. and location
n -= 2; // set parameter to n-2
goto line 0; // goto start of method
We replace line 5, handling the return, with the following.
5: if ([Link]()) return retVal; // top-level return
<P1,P2,n,label> = [Link](); // set from popped values
if (label == 3)
P1 = retVal; // set P1 to value returned from fib( n-1 )
else
P2 = retVal; // set P2 to value returned from fib( n-2 )
goto label;
Note that line 5 is the general "return" procedure and we can use it for returning from
our base cases (we don't need to write this part of the code again). So lines 0 and 1 get
replaced with the following.
0: if (n == 0)
{
retVal = 0;
goto 5;
}
1: if (n == 1)
{
retVal = 1;
goto 5;
}
Putting all of this together, the code is a morass of gotos heading every which way. We
can get rid of a goto that heads back earlier in the code by introducing a loop instead.
With some more work perhaps you could probably get rid of other gotos as well. But I
won't go that route. This yields our final method which is shown in its entirety in the
attached C++ source file. The file is actually a complete program that contains an
implementation of the StackItem class and a main method that calls the iterative
fibonacci method. You can run it to verify that it really does compute the fibonacci
numbers, if you wish
This iterative fibonacci method computes the fibonacci numbers using the exact same
algorithm that the simple recursive method does. It makes the exact same calculations
as the original recursive version. There is very little difference in their execution time
but the original recursive method is obviously much simpler. If I were to hand you the
attached program with no explanations nor comments, you would have no idea of what
it does from a brief read. It is almost indecipherable. Compare that to the simplicity of
the recursive method which follows fairly trivially from its recursive definition.