Mit einem Schwanz -rekursiven Funktionsaufruf kann der Compiler eine spezielle Optimierung durchführen, die er normalerweise nicht mit regelmäßiger Rekursion kann. In einer rekursiven Schwanzfunktion ist der rekursive Anruf das allerletzte, was ausgeführt werden muss. In diesem Fall kann der Compiler den Code überarbeiten, um den aktuellen Stapelrahmen einfach wiederzuverwenden, anstatt einen Stapelrahmen für jeden Aufruf zuzuweisen, was bedeutet, dass eine Heckrekursivfunktion nur einen einzelnen Stapelrahmen verwendet, im Gegensatz zu Hunderten oder sogar Tausenden.
Diese Optimierung ist möglich, da der Compiler weiß, dass sobald der schwanzrekursive Anruf getätigt wurde, keine früheren Kopien von Variablen benötigt werden, da kein Code mehr auszuführen ist. Wenn beispielsweise eine Druckanweisung einem rekursiven Anruf folgte, müsste der Compiler den Wert der Variablen kennen, die nach dem rekursiven Anruf zurückgegeben werden soll, und somit kann der Stapelrahmen nicht wiederverwendet werden.
Hier ist die Wiki -Seite, wenn Sie weitere Informationen darüber wünschen, wie diese "Raumsparen" und Stapelreue tatsächlich funktioniert, zusammen mit Beispielen: Schwanzanruf
EDIT: Ich habe nicht erklärt, wie dies für Quicksort gilt, oder? Nun, einige Begriffe werden in diesem Artikel herumgeworfen, der alles verwirrend macht (und einige davon sind einfach falsch). Die erste Funktion (QuickSort) macht links einen rekursiven Anruf, einen rekursiven Anruf rechts und beendet dann. Beachten Sie, dass der rekursive Anruf rechts das allerletzte ist, was in der Funktion passiert. Wenn der Compiler eine rekursive Optimierung der Schwanz unterstützt (oben erläutert), erzeugen nur die linken Anrufe neue Stapelrahmen. Die richtigen Anrufe verwenden einfach den aktuellen Rahmen wieder. Dies kann sparen etwas Stackrahmen, kann aber immer noch unter dem Fall leiden, in dem die Partitionierung eine Folge von Aufrufen erzeugt, bei denen die Heckrekursionsoptimierung keine Rolle spielt. Auch wenn die rechten Anrufe denselben Rahmen verwenden, rufen die linken Anrufe auf innerhalb Die rechten Anrufe verwenden immer noch den Stapel. Im schlimmsten Fall ist die Stapeltiefe N.
Die beschriebene zweite Version ist nicht Ein schwanzrekursiver Quicksort, sondern eine Quicksort, bei der nur die linke Sortierung rekursiv durchgeführt wird und die richtige Sortierung mit der Schleife durchgeführt wird. Tatsächlich kann diese Quicksort (wie zuvor von einem anderen Benutzer beschrieben) nicht die Schwanzrekursionsoptimierung angewendet haben, da der rekursive Anruf nicht das Letzte ist, was man ausführen kann. Wie funktioniert das? Bei korrekter Implementierung entspricht der erste Anruf bei QuickSort wie ein Aufruf der linken Seite im ursprünglichen Algorithmus. Es werden jedoch sogar keine rekursiven Aufrufe der rechten Seite aufgerufen. Wie funktioniert das? Nun, die Schleife kümmert sich darum: Anstatt "links dann rechts" zu sortieren, sortiert sie die linke mit einem Anruf und sortiert dann das rechte linke der rechten. Es klingt wirklich lächerlich, aber es ist im Grunde genommen nur so viele Links sortiert, dass die Rechte zu einzelnen Elementen werden und nicht sortiert werden müssen. Dadurch wird die richtige Rekursion effektiv entfernt, wodurch die Funktion weniger rekursiv wird (Pseudo rekursiv, wenn Sie so wollen). Die tatsächliche Implementierung wählt jedoch nicht jedes Mal die linke Seite. Es wählt die kleinste Seite. Die Idee ist immer noch dieselbe; Grundsätzlich nur ein rekursiver Anruf auf einer Seite statt auf beiden. Durch die Auswahl der kürzeren Seite wird sichergestellt, dass die Stapeltiefe niemals größer als log2 (n) sein kann, was die Tiefe eines ordnungsgemäßen Binärbaums ist. Dies liegt daran, dass die kürzere Seite immer höchstens halb so groß ist wie unser aktueller Array -Abschnitt. Die durch den Artikel angegebene Implementierung gewährleistet dies jedoch nicht, da er unter dem gleichen Worst-Case-Szenario von "Links ist der ganze Baum" leiden kann. Dieser Artikel gibt tatsächlich eine ziemlich gute Erklärung dafür, wenn Sie bereit sind, mehr zu lesen: Effiziente Auswahl und teilweise Sortierung basierend auf Quicksort