Was ist Schwanzrekursion?

Die Schwanzrekursion ist ein Sonderfall der Rekursion, bei dem die aufrufende Funktion nach einem rekursiven Aufruf keine Berechnung mehr durchführt. Beispielsweise ist die Funktion

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

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 nach der Rückkehr des rekursiven Aufrufs einige Berechnungen durchgeführt werden.

Die Schwanzrekursion ist wichtig, da sie effizienter implementiert werden kann als die allgemeine Rekursion. Wenn wir einen normalen rekursiven Aufruf tätigen, müssen wir die Rücksprungadresse auf den Aufrufstapel verschieben 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 vom rekursiven Aufruf zurückkehren, ebenfalls sofort zurückkehren werden, sodass wir die gesamte Kette der rekursiven Funktionen, die zurückkehren, überspringen und direkt zum ursprünglichen Aufrufer zurückkehren können. Das heißt, wir ziehen nicht an „Ich benötige überhaupt keinen Aufrufstapel für alle rekursiven Aufrufe und kann den letzten Aufruf als einfachen Sprung implementieren, was uns Platz spart.

Kommentare

• Sie haben “ geschrieben. Das heißt, wir ‚ benötigen überhaupt keinen Aufrufstapel für alle rekursiven Aufrufe „. Call Stack wird immer da sein, nur dass die Absenderadresse nicht in den Call Stack geschrieben werden muss, oder?
• Es hängt bis zu einem gewissen Grad von Ihrem Rechenmodell ab 🙂 Aber ja, auf einem echten Computer ist das Der Aufrufstapel ist noch vorhanden. Wir ‚ verwenden ihn einfach nicht.
• Was ist, wenn ‚ das Finale ist? call aber in for for Schleife. Sie führen also alle oben genannten Berechnungen durch, einige jedoch in einer for-Schleife wie def recurse(x): if x < 0 return 1; for i in range 100{ (do calculations) recurse(x)}
• @ thed0ctor – diese rekursive Methode ist nicht ‚ t terminate.

Einfach gesagt, die Schwanzrekursion ist eine Rekursion, die der Compiler ersetzen könnte Der rekursive Aufruf mit einem „goto“ -Befehl, sodass die kompilierte Version die Stapeltiefe nicht erhöhen muss.

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

Dies ist beispielsweise keine rekursive Schwanzfunktion:

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

Dies ist jedoch eine Schwanzrekursivfunktion. rekursive 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; } 

, da der Compiler die rekursive Funktion unter Verwendung der folgenden (Pseudocode) in eine nicht rekursive Funktion umschreiben könnte:

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 „

„. 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 einen Tail -rekursive Funktion.

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))) 

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 eine rekursive Prozedur ist. Es sollte auch beachtet werden, dass bei diesem Ansatz eine festgelegte Variable den Status 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 versteckte Informationen, die der Interpreter verwaltet, was im Grunde die Kette von verzögerten Operationen ist.

Kommentare

• ‚ sollte nicht nur (1) anstelle von (* 1)?

Schwanzrekursion ist eine Form der Rekursion, bei der die rekursiven Aufrufe die letzten Anweisungen in der Funktion sind (von denen der Endteil stammt). Außerdem darf der rekursive Aufruf nicht aus Verweisen auf Speicherzellen bestehen, in denen vorherige Werte gespeichert sind (andere Verweise als die Parameter der Funktion). 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 andere Optimierung besteht darin, dass es eine einfache Möglichkeit gibt, einen rekursiven Algorithmus in einen äquivalenten Algorithmus umzuwandeln, der Iteration anstelle von Rekursion verwendet. Ja, der Algorithmus für Quicksort ist in der Tat schwanzrekursiv.

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