Was ist Schwanzrekursion?

52

Ich kenne das allgemeine Konzept der Rekursion. Beim Studium des Quicksort-Algorithmus bin ich auf das Konzept der Schwanzrekursion gestoßen. In diesem Video von Quick Sort Algorithmus vom MIT um 18:30 Sekunden sagt der Professor, dass dies ein rekursiver Schwanzalgorithmus ist. Mir ist nicht klar, was Schwanzrekursion wirklich bedeutet.

Kann jemand das Konzept mit einem richtigen Beispiel erklären?

Einige Antworten der SO-Community hier .

Aussenseiter
quelle
Erzählen Sie uns mehr über den Kontext, in dem Sie auf den Begriff Schwanzrekursion gestoßen sind . Verknüpfung? Zitat?
A.Schulz
@ A.Schulz Ich habe den Link zum Kontext gesetzt.
Geek
5
Schauen Sie sich " Was ist Schwanzrekursion? " Bei Stackoverflow an
Vor
2
@ajmartin Die Frage ist grenzwertig Stack - Überlauf , aber fest auf dem Thema auf Informatik , so im Prinzip Informatik sollten bessere Antworten produzieren. Es ist hier nicht passiert, aber es ist in Ordnung, hier erneut zu fragen, in der Hoffnung auf eine bessere Antwort. Geek, du hättest deine frühere Frage zu SO erwähnen sollen, damit die Leute nicht wiederholen, was bereits gesagt wurde.
Gilles 'SO- hör auf böse zu sein'
1
Sie sollten auch sagen, was mehrdeutig ist oder warum Sie mit früheren Antworten nicht zufrieden sind. Ich denke, SO geben die Leute gute Antworten, aber was hat Sie dazu veranlasst, es erneut zu fragen?

Antworten:

52

Die Schwanzrekursion ist ein Sonderfall der Rekursion, bei dem die aufrufende Funktion nach einem rekursiven Aufruf keine Berechnung mehr vornimmt. Zum Beispiel die Funktion

int f (int x, int y) {
  if (y == 0) {
    return x;
  }

  return f (x * y, y-1);
}

ist rekursiv (da der letzte Befehl ein rekursiver Aufruf ist), während diese Funktion nicht rekursiv ist:

int g (int x) {
  if (x == 1) {
    return 1;
  }

  int y = g (x-1);

  return x * y;
}

da es einige Berechnungen durchführt, nachdem der rekursive Aufruf zurückgekehrt ist.

Die Schwanzrekursion ist wichtig, da sie effizienter implementiert werden kann als die allgemeine Rekursion. Wenn wir einen normalen rekursiven Aufruf machen, müssen wir die Rücksprungadresse auf den Aufrufstapel legen und dann zur aufgerufenen Funktion springen. Dies bedeutet, dass wir einen Aufrufstapel benötigen, dessen Größe in der Tiefe der rekursiven Aufrufe linear ist. Wenn wir eine Schwanzrekursion haben, wissen wir, dass wir, sobald wir von dem rekursiven Aufruf zurückkehren, auch sofort zurückkehren, sodass wir die gesamte Kette rekursiver Funktionen, die zurückkehren, überspringen und direkt zum ursprünglichen Aufrufer zurückkehren können. Das bedeutet, dass wir für alle rekursiven Aufrufe überhaupt keinen Aufrufstapel benötigen und den endgültigen Aufruf als einfachen Sprung implementieren können, wodurch Platz gespart wird.

Matt Lewis
quelle
2
Sie haben geschrieben: "Das heißt, wir brauchen überhaupt keinen Aufrufstapel für alle rekursiven Aufrufe." Callstack wird immer da sein, nur dass die Absenderadresse nicht in den Callstack geschrieben werden muss, oder?
Geek
2
Es hängt bis zu einem gewissen Grad von Ihrem Rechenmodell ab :) Aber ja, auf einem echten Computer ist der Aufrufstapel immer noch vorhanden, wir verwenden ihn nur nicht.
Matt Lewis
Was ist, wenn es der letzte Anruf ist, aber in der for for-Schleife. Also machst du alle deine obigen Berechnungen, aber einige von ihnen in einer for-Schleife wiedef recurse(x): if x < 0 return 1; for i in range 100{ (do calculations) recurse(x)}
thed0ctor
13

Einfach gesagt, ist die Schwanzrekursion eine Rekursion, bei der der Compiler den rekursiven Aufruf durch einen "goto" -Befehl ersetzen könnte, sodass die kompilierte Version die Stapeltiefe nicht erhöhen muss.

Manchmal müssen Sie zum Entwerfen einer rekursiven Endfunktion eine Hilfsfunktion mit zusätzlichen Parametern erstellen.

Dies ist beispielsweise keine Schwanzrekursivfunktion:

int factorial(int x) {
    if (x > 0) {
        return x * factorial(x - 1);
    }
    return 1;
}

Dies ist jedoch eine schwanzrekursive Funktion:

int factorial(int x) {
    return tailfactorial(x, 1);
}

int tailfactorial(int x, int multiplier) {
    if (x > 0) {
        return tailfactorial(x - 1, x * multiplier);
    }
    return multiplier;
}

weil der Compiler die rekursive Funktion in eine nicht rekursive Funktion umschreiben könnte, indem er so etwas wie diesen (einen Pseudocode) verwendet:

int tailfactorial(int x, int multiplier) {
    start:
    if (x > 0) {
        multiplier = x * multiplier;
        x--;
        goto start;
    }
    return multiplier;
}

Die Regel für den Compiler ist sehr einfach: Wenn Sie " return thisfunction(newparameters);" finden, ersetzen Sie sie durch " parameters = newparameters; goto start;". Dies ist jedoch nur möglich, wenn der vom rekursiven Aufruf zurückgegebene Wert direkt zurückgegeben wird.

Wenn alle rekursiven Aufrufe in einer Funktion auf diese Weise ersetzt werden können, handelt es sich um eine rekursive Endfunktion.

Viliam Búr
quelle
13

Meine Antwort basiert auf der Erklärung im Buch Struktur und Interpretation von Computerprogrammen . Ich kann dieses Buch Informatikern nur empfehlen.

Ansatz A: Linearer rekursiver Prozess

(define (factorial n)
 (if (= n 1)
  1
  (* n (factorial (- n 1)))))

Die Form des Prozesses für Ansatz A sieht folgendermaßen aus:

(factorial 5)
(* 5 (factorial 4))
(* 5 (* 4 (factorial 3)))
(* 5 (* 4 (* 3 (factorial 2))))
(* 5 (* 4 (* 3 (* 2 (factorial 1)))))
(* 5 (* 4 (* 3 (* 2 (* 1)))))
(* 5 (* 4 (* 3 (* 2))))
(* 5 (* 4 (* 6)))
(* 5 (* 24))
120

Ansatz B: Linearer iterativer Prozess

(define (factorial n)
 (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
 (if (> counter max-count)
  product
  (fact-iter (* counter product)
             (+ counter 1)
             max-count)))

Die Form des Prozesses für Ansatz B sieht folgendermaßen aus:

(factorial 5)
(fact-iter 1 1 5)
(fact-iter 1 2 5)
(fact-iter 2 3 5)
(fact-iter 6 4 5)
(fact-iter 24 5 5)
(fact-iter 120 6 5)
120

Der lineare iterative Prozess (Ansatz B) wird im konstanten Raum ausgeführt, obwohl der Prozess ein rekursiver Prozess ist. Es sollte auch beachtet werden, dass bei diesem Ansatz eine festgelegte Variable den Zustand des Prozesses an jedem Punkt definiert, nämlich. {product, counter, max-count}. Dies ist auch eine Technik, mit der die Schwanzrekursion die Compileroptimierung ermöglicht.

In Ansatz A gibt es mehr verborgene Informationen, die der Interpreter verwaltet. Dies ist im Grunde die Kette der zurückgestellten Operationen.

Ajmartin
quelle
5

Die Schwanzrekursion ist eine Form der Rekursion, bei der die rekursiven Aufrufe die letzten Anweisungen in der Funktion sind (daher kommt der Schwanzteil). Darüber hinaus darf der rekursive Aufruf nicht aus Referenzen auf Speicherzellen bestehen, in denen vorherige Werte gespeichert sind (Referenzen, die keine Parameter der Funktion sind). Auf diese Weise kümmern wir uns nicht um vorherige Werte, und ein Stapelrahmen reicht für alle rekursiven Aufrufe aus. Die Schwanzrekursion ist eine Möglichkeit, rekursive Algorithmen zu optimieren. Der andere Vorteil / die Optimierung besteht darin, dass es eine einfache Möglichkeit gibt, einen rekursiven Algorithmus für den Schwanz in einen äquivalenten Algorithmus umzuwandeln, der Iteration anstelle von Rekursion verwendet. Also ja, der Algorithmus für Quicksort ist in der Tat rekursiv.

QUICKSORT(A, p, r)
    if(p < r)
    then
        q = PARTITION(A, p, r)
        QUICKSORT(A, p, q–1)
        QUICKSORT(A, q+1, r)

Hier ist die iterative Version:

QUICKSORT(A)
    p = 0, r = len(A) - 1
    while(p < r)
        q = PARTITION(A, p, r)
        r = q - 1

    p = 0, r = len(A) - 1
    while(p < r)
        q = PARTITION(A, p, r)
        p = q + 1
Saadtaame
quelle