To convert a recursive method to a non-recursive one, we use a stack and manually
follow the spirit of the steps outlined in file [Link]. To illustrate this, consider
the book's recursive fibonacci method. The method is as follows.
public static 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.
public static 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). To do this, we write a StackItem class which has four private data members
for storing these values. The needed methods 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. Java doesn't have a goto statement but we can achieve the same
effect. Use a variable goto_ that stores the labels. Use a switch( goto_ )
statement where the case values are the code labels. For cases that get executed
consecutively (like 0 and 1), we let the flow of control fall through to the next case. To
handle a goto, we set the variable goto_ to the appropriate value followed by a break.
To execute the switch again with the new goto_ value, we place the switch in a loop.
This yields our final method which is shown in its entirety in the attached java 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. (The
reason I didn't use goto as the variable name is because goto is a reserved word in
Java despite the fact that the goto statement was never implemented!).
This iterative fibonacci method computes the fibonacci numbers using the exact same
inefficient algorithm that the simple recursive method does. It makes the exact same
calculation repetitions that the original recursive method does. 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.
The final truth is that anything that can be written recursively can be written iteratively
and vice-versa. If you wanted to, you could eliminate recursion from a programming
language or eliminate iteration, and you will still be able to compute everything that you
could before (as examples, the original version of Fortran did not have recursion and
the original version of LISP did not have iteration.). Iteration is generally slightly more
efficient (say 5%) because there is less overhead in controlling a loop than there is in
calling and returning from a method. In most cases the efficiency difference is not worth
worrying about. Just use whichever happens to be simplest for the task at hand. The
simpler one will be easier to understand, write, and debug.