Umschreiben einer rekursiven Funktion ohne Verwendung der Rekursion

Question

Ich schreibe einen bestehenden Code in einer Umgebung um, in der rekursive Aufrufe weder einfach implementiert noch gewünscht sind. (Und in Fortran 77, falls Sie es wissen müssen.) Ich habe darüber nachgedacht, einen Stack von Grund auf neu zu erstellen, um die benötigten Aufrufe im Auge zu behalten, aber das scheint umständlich zu sein, und ich würde lieber keinen Speicher für ein Array in Fällen zuweisen, in denen die Rekursion nicht tief ist. (Ich bin nicht zuversichtlich, dass Fortran 77 auch dynamische Array-Größe unterstützt.)

Irgendwelche anderen Vorschläge für eine allgemeine Lösung, wie man eine offensichtlich rekursive Funktion nimmt und sie nicht-rekursiv umschreibt, ohne Platz auf einem Stapel zu verschwenden?

Vielen Dank! Alter McSt

Answer 1

Wenn Ihr Code Tail-Rekursion verwendet (d.h. die Funktion gibt das Ergebnis jedes rekursiven Aufrufs direkt zurück, ohne weitere Verarbeitung), dann ist es möglich, die Funktion zwingend ohne Stack umzuschreiben:

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

In:

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

Ohne Tail-Rekursion ist die Verwendung eines Stacks (oder eines ähnlichen Zwischenspeichers) die einzige Lösung.

Answer 2

Die klassische rekursive Funktion, die als Schleife geschrieben werden kann, ist die Fibonacci-Funktion:

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

Ohne Memoisierung erfordert dies jedoch O(exp^N) Operationen mit O(N) Stapelplatz.

Sie kann umgeschrieben werden:

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

Dazu muss man jedoch wissen, wie die Funktion funktioniert. Ich bin mir nicht sicher, ob dies auf einen automatischen Prozess verallgemeinert werden kann.

Answer 3

Die meisten rekursiven Funktionen können leicht in Schleifen umgeschrieben werden, um Platz zu sparen - das hängt von der Funktion ab, da viele (aber nicht alle) rekursive Algorithmen tatsächlich auf diese Art von Speicher angewiesen sind (obwohl die Schleifenversion auch in diesen Fällen normalerweise effizienter ist).