La reescritura de una función recursiva sin utilizar la recursividad

Question

Estoy volver a escribir algo de código existente en un entorno en el que las llamadas recursivas no se implementan fácilmente ni deseados. (Y en Fortran 77, si quieres saberlo.) He pensado en hacer una pila a partir de cero para realizar un seguimiento de las llamadas necesarias, pero esto parece kludgy, y yo preferiría no asignar memoria para un array en los casos en que la recursividad no es profunda. (No estoy seguro de que Fortran 77 soportes matriz dinámica de encolado tampoco.)

¿Alguna otra sugerencia para una solución general sobre cómo tomar una función recursiva, obviamente, y volver a escribir que no recursiva sin desperdiciar espacio en una pila?

Muchas gracias, Antiguo 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).