Rewriting a recursive function without using recursion

Question

I'm rewriting some existing code in a setting where recursive calls are not easily implemented nor desired. (And in Fortran 77, if you must know.) I've thought about making a stack from scratch to keep track of the calls needed, but this seems kludgy, and I'd rather not allocate memory to an array in cases where the recursion is not deep. (I'm not confident that Fortran 77 supports dynamic array sizing either.)

Any other suggestions for a general solution on how to take an obviously recursive function and rewrite it non-recursively without wasting space on a stack?

Many thanks, Old McSt

Answer 1

If your code uses tail recursion (that is, the function returns the result of every recursive call directly without any other processing) then it's possible to rewrite the function imperatively without a stack:

function dosomething(a,b,c,d) 
{
  // manipulate a,b,c,d
  if (condition) 
    return dosomething(a,b,c,d) 
  else
    return something;
}

Into:

function dosomething(a,b,c,d) 
{
  while (true) 
  {
    // manipulate a,b,c,d
    if (condition) continue;
    else return something;
  }
}

Without tail recursion, using a stack (or a similar intermediary storage) is the only solution.

Answer 2

The classic recursive function that can be written as a loop is the Fibonacci function:

 function fib(n)
 {
     // valid for n >= 0
     if (n < 2)
         return n;
     else
         return fib(n-1) + fib(n-2);
 }

But without memoization this takes O(exp^N) operations with O(N) stack space.

It can be rewritten:

 function fib(n)
 {
     if (n < 2)
        return n;
     var a = 0, b = 1;
     while (n > 1)
     {
         var tmp = a;
         a = b;
         b = b + tmp;
         n = n - 1;
     }   
     return b;
 }

But this involves knowledge of how the function works, not sure if it can be generalized to an automatic process.

Answer 3

Most recursive functions can be easily rewritten as loops, as to wasting space - that depends on the function, since many (but not all) recursive algorithms actually depend on that kind of storage (although, the loop version is usually more efficient in these cases too).