Riscrittura di una funzione ricorsiva senza utilizzare ricorsione

Question

Sto riscrivendo qualche codice esistente in un ambiente dove le chiamate ricorsive non sono facilmente implementati né desiderato. (E in Fortran 77, se proprio vuoi saperlo.) Ho pensato di fare una pila da zero per tenere traccia delle chiamate necessarie, ma questo sembra kludgy, e io non preferisce allocare memoria per un array in casi in cui il ricorsione non è profonda. (Io non sono sicuro che Fortran 77 supporta array dinamico dimensionamento sia.)

Altri suggerimenti per una soluzione generale su come prendere una funzione ricorsiva, ovviamente, e riscriverlo non ricorsivo senza sprecare spazio su una pila?

Molte grazie, Vecchio MCST

Answer 1

Se il codice utilizza ricorsione di coda (che è, la funzione restituisce il risultato di ogni chiamata ricorsiva direttamente senza qualsiasi altra elaborazione) allora è possibile riscrivere la funzione imperativamente, senza uno 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;
  }
}

Senza coda ricorsione, utilizzando uno stack (o un'itermedie simile) è l'unica soluzione.

Answer 2

La funzione ricorsiva classico che può essere scritta come un ciclo è la funzione di Fibonacci:

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

Ma senza memoization questo richiede O (exp ^ N) operazioni con O (N) spazio dello stack.

Si può essere riscritta:

 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;
 }

Ma questo comporta la conoscenza di come funziona la funzione, non è sicuro se può essere generalizzato a un processo automatico.

Answer 3

La maggior parte delle funzioni ricorsive può essere facilmente riscritto come loop, come allo spazio sprecare - che dipende dalla funzione, dal momento che molti (ma non tutti) ricorsiva algoritmi in realtà dipendono da questo tipo di stoccaggio (anche se, la versione del ciclo di solito è più efficiente anche in questi casi).