Réécriture une fonction récursive sans utiliser récursion

Question

Je réécriture du code existant dans un contexte où les appels récursifs ne sont pas facilement mises en œuvre ni désiré. (Et en Fortran 77, si vous devez savoir.) Je l'ai pensé à faire une pile à partir de zéro pour garder la trace des appels nécessaires, mais cela semble kludgy, et je préfère ne pas allouer de la mémoire à un tableau dans les cas où la récursion est peu profonde. (Je ne suis pas sûr que Fortran 77 supports dimensionnement tableau dynamique non plus.)

Toutes les autres suggestions pour une solution générale sur la façon de prendre une fonction récursive et évidemment réécrire non récursive sans gaspiller l'espace sur une pile?

Merci, Old MCST

Answer 1

Si votre code utilise la récursivité queue (qui est, la fonction retourne le résultat de chaque appel récursif directement, sans aucun autre traitement), il est possible de réécrire la fonction sans pile impérieusement:

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

Dans:

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

Sans récursion arrière, en utilisant une pile (ou un stockage intermédiaire similaire) est la seule solution.

Answer 2

La fonction récursive classique qui peut être écrit en boucle est la fonction Fibonacci:

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

Mais sans memoization cela prend O (exp ^ N) avec O (N) d'espace de pile.

Il peut être réécrite:

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

Mais cela implique la connaissance de la façon dont les travaux de la fonction, ne sais pas si elle peut être généralisée à un processus automatique.

Answer 3

La plupart des fonctions récursives peut facilement être réécrite sous forme de boucles, à l'espace débilitante - qui dépend de la fonction, puisque beaucoup (mais pas tous) des algorithmes récursifs dépendent en fait de ce type de stockage (bien que, la version en boucle est généralement plus efficace dans ces cas aussi).