Umschreiben einer rekursiven Funktion, ohne Verwendung von Rekursion

Bin ich umschreiben einige der bestehenden code in eine Einstellung, wo rekursive Aufrufe sind nicht so leicht umgesetzt noch angestrebt. (Und in Fortran 77, wenn Sie müssen wissen.) Ich habe gedacht, darum, einen Stapel von Grund auf zu verfolgen, Anrufe, notwendig, aber dieses scheint notdürftigem, und ich möchte lieber nicht reserviert Speicher für ein array in Fällen, in denen die Rekursion ist nicht tief. (Ich bin nicht überzeugt, dass Fortran 77 unterstützt das dynamische array-Dimensionierung entweder.)

Andere Vorschläge für eine Allgemeine Lösung auf, wie Sie ein offensichtlich rekursive Funktion und schreiben Sie es nicht-rekursiv ohne Platzverschwendung auf ein stack?

Vielen Dank,
Alte McSt

  • Wenn es nicht verzweigen, können Sie in der Regel schreiben Sie in einer einfachen Schleife. Wenn es Zweige, die Sie benötigen in der Regel einen Stapel
  • eine rekursive Funktion, die nicht verzweigen, wird, per definition, nie wieder...
  • Denke, dass ich missbraucht das Wort Zweig. Ich meine, selbst mehrere Male aufgerufen, so dass der graph der Aufrufe wird zu einem Baum mit ästen. Und es ist nur meine Erfahrung und nicht immer wahr.
InformationsquelleAutor Old McStopher | 2010-12-12
  1. 15

    Wenn Ihr code verwendet tail-Rekursion (das heißt, die Funktion gibt das Ergebnis eines jeden rekursiven Aufrufs direkt, ohne jede weitere Verarbeitung), dann ist es möglich, zu schreiben, die Funktion zwingend ohne stack:

    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, mit einem stack (oder eine ähnliche Zwischenlagerung) ist die einzige Lösung.

    • Dies ist ähnlich zu dem, was ich dachte, aber konnte nicht in Worte fassen. Also in meinem konkreten Falle habe ich einen Daten-Satz von Elementen, die jeweils geprüft werden müssen, für eine Beziehung zu anderen Elementen im Satz. Ich könnte passieren in der Datenstruktur alle Elemente, da aber jeder Bedarf einer weiteren Verarbeitung, ich nehme an, der stack ist unvermeidlich, ja?
    • Hängt davon ab. Wenn der code meist "für alle Paare (a,b), falls P(a,b) wahr ist, dann führen F(a,b)" Sie können sich mit iterativ Durchlaufen alle Paare...
    InformationsquelleAutor Victor Nicollet
  2. 3

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

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

    Aber ohne memoization dies dauert O(exp^N) Operationen mit O(N) stack-Speicher.

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

    Aber das beinhaltet das wissen, wie die Funktion arbeitet, nicht sicher, ob es verallgemeinert werden kann, um einen automatischen Prozess.

    InformationsquelleAutor Jason S
  3. 2

    Meisten rekursiven Funktionen leicht umgeschrieben, als Schleifen, als auf Platz verschwenden - das hängt von der Funktion ab, da viele (aber nicht alle) rekursive algorithmen tatsächlich davon abhängen, die Art der Speicherung (obwohl, die loop-version ist in der Regel effizienter in diesen Fällen auch).

    • Care zu zeigen Sie eine rekursive Funktion, die nicht erfordern keinen Platz auf stack? Auch für seine Argumente?
    • Rybak : ein inline tail-rekursive Funktion 😉
    • Ja, aber das ist in der form umgeschrieben. Und Ofir Ansprüche es gibt eine rekursive Funktion, die nicht erfordern, stack-Speicher. So, ich bin gespannt.
    • siehe meine Antwort.
    • Sind Sie sagen, dass die rekursive Funktion nicht "abhängen, die Art der Lagerung"?
    • Kontrast ist ein rekursiver Algorithmus, eine rekursive Implementierung der Algorithmus. Letzteres erfordert immer Stapelspeicher, wenn nicht ein Beispiel tail recursion. Der ehemalige hängt davon ab, wie es umgesetzt wird.

    InformationsquelleAutor Ofir
Schreibe einen Kommentar