Was ist der Vorteil der Verwendung der Schwanzrekursion hier?

Question 1

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

Question 2

Der Vorteil, der springende Punkt der "gemischten rekursiven/iterativen" Version, dh eine Version, die eine Unterabteilung durch Rekursion und einen anderen Unterbereich durch Iteration verarbeitet garantieren, dass die Tiefe der Rekursion niemals überschreiten wird log2 N, unabhängig davon, wie schlimm die Pivot -Wahl ist.

Für die TAIL-RECURSIVE-QUICKSORT Pseudocode in der Frage, in der die rekursive Verarbeitung zunächst durch einen wörtlichen rekursiven Aufruf durchgeführt wird, sollte der rekursive Anruf gegeben werden kürzer Unterabschnitt. Das alleine wird sicherstellen, dass die Rekursionstiefe durch begrenzt wird log2 N. Um die Rekursionstiefe zu erreichen, muss der Code unbedingt die Längen der Unterbereitungen vergleichen, bevor er entscheidet, welcher Unterbereich durch rekursives Anruf zu verarbeiten ist.

Eine ordnungsgemäße Implementierung dieses Ansatzes könnte wie folgt aussehen (das Ausleihen Ihres Pseudocode als Ausgangspunkt)

HALF-RECURSIVE-QUICKSORT(A, p, r)
   while p < r
      q = PARTITION(A, p, r)
      if (q - p < r - q)
        HALF-RECURSIVE-QUICKSORT(A, p, q-1)
        p = q+1
      else
        HALF-RECURSIVE-QUICKSORT(A, q+1, r)
        r = q-1

Das TAIL-RECURSIVE-QUICKSORT Pseudocode, das Sie bereitgestellt haben, unternimmt keine Versuche, die Längen der Unterbereiche zu vergleichen. In diesem Fall bietet es keinerlei Nutzen. Und nein, es ist nicht wirklich "Schwanz rekursiv". Quicksort kann unmöglich auf einen schwanzrezisiven Algorithmus reduziert werden.

Wenn Sie eine Google-Suche zu den Begriffen "Qsort Loguy Higuy" durchführen . Diese Implementierung für 32 -Bit -Plattformen verwendet explizite Stapel mit maximaler Tiefe von ~ 32, insbesondere weil sie garantieren kann, dass die Rekursionstiefe niemals höher wird. (In ähnlicher Weise benötigen 64 -Bit -Plattformen nur eine Stapel -Tiefe von ~ 64.)

Das QUICKSORT Version, die zwei wörtliche rekursive Anrufe verschlechtert, ist in dieser Hinsicht erheblich schlechter N im schlimmsten Fall. Mit zwei rekursiven Anrufen können Sie nicht garantieren, dass die Rekursionstiefe durch begrenzt ist durch log2 N. Ein intelligenter Compiler kann den nachverfolgenden Anruf möglicherweise ersetzen QUICKSORT Mit Iteration drehen Sie Ihre QUICKSORT in dein TAIL-RECURSIVE-QUICKSORT, aber es wird nicht klug genug sein, den Vergleich der Unterabteilung Länge durchzuführen.

Question 3

Vorteil der Verwendung der Schwanzrezision: = damit der Compiler den Code optimiert und in einen nicht rekursiven Code umwandelt.

Vorteil des nicht recursiven Codes gegenüber rekursiver: = Der nicht rekursive Code erfordert weniger Speicher, um auszuführen als eine rekursive. Dies liegt an Leerlaufstapelrahmen, die die Rekursion verbraucht.

Hier kommt der interessante Teil:- obwohl die Compiler kann Theoritische Durchführung dieser Optimierung, sie in der Praxis nicht. Sogar die weit verbreiteten Compiler wie Dot-Net und Java führen diese Optimierung nicht durch.

Ein Problem, mit dem alle Code-Optimierungen konfrontiert sind, ist das Opfer in der Debugabilität. Der optimierte Code entspricht nicht mehr dem Quellcode, sodass Stapelspuren und Ausnahmetails nicht leicht zu verstehen sind. Hochleistungscode oder wissenschaftliche Anwendungen sind eine Sache, aber für die Mehrheit des Debuggens von Verbraucheranwendungen ist auch nach der Veröffentlichung erforderlich. Daher werden Optimierungen nicht so energisch durchgeführt.

Bitte siehe:

Question 4

Es scheint hier einige Vokabeln zu geben.

Die erste Version ist schwanzrezisiv, da die letzte Aussage ein rekursiver Anruf ist:

QUICKSORT(A, p, r)
  q = PARTITION(A, p, r)
  QUICKSORT(A, p, q-1)
  QUICKSORT(A, q+1, r)

Wenn Sie die Heckrezisionsoptimierung anwenden, die die Rekursion in eine Schleife umwandeln soll, erhalten Sie den zweiten, was nicht mehr mit dem Schwanz rekursiv ist:

TAIL-RECURSIVE-QUICKSORT(A, p, r)
  while p < r
    q = PARTITION(A, p, r)
    TAIL-RECURSIVE-QUICKSORT(A, p, q-1)
    p = q+1

Der Vorteil davon ist, dass Sie normalerweise weniger Stapelspeicher benötigen. Warum ist das so? Stellen Sie sich vor, Sie möchten ein Array mit 31 Elementen sortieren. In dem sehr unwahrscheinlichen Fall, dass alle Partitionen perfekt sind, würden sie das Array direkt in der Mitte teilen. Ihre Rekursionstiefe würde 4 sein. In der Tat würde die erste Trennung zwei Partitionen von 15 Elementen ergeben, die zweite zwei Partitionen von 7 Elementen, Die dritte zwei von 3 Artikeln und nach dem vierten ist alles sortiert.

Aber Partitionen sind selten so perfekt. Infolgedessen gehen nicht alle Rekursionen gleich tief. In unserem Beispiel haben Sie möglicherweise einige, die nur drei Ebenen tief sind, und einige, die 7 oder mehr sind (schlimmster Fall ist 30). Durch die Beseitigung der Hälfte der Rekursionen haben Sie eine faire Chance, dass Ihre maximale Rekursionstiefe geringer ist.

Wie Andreyt betonte, werden häufig die Bereiche verglichen, um sicherzustellen, dass die größte Partition immer iterativ verarbeitet wird und die kleinste rekursiv. Dies garantiert die kleinstmögliche Rekursionstiefe für eine bestimmte Strategie für Eingabe- und Pivot -Auswahl.

Dies ist jedoch nicht immer der Fall. Manchmal möchten die Menschen so bald wie möglich Ergebnisse erzielen oder nur die ersten nelemente finden und sortieren. In diesen Fällen wollen sie immer die erste Trennwand vor dem zweiten sortieren. Selbst in dieser Situation verbessert die Beseitigung der Schwanzrekursion normalerweise die Speicherverwendung und macht es nie noch schlimmer.

Question 5

Ich weiß nicht genau, ob dies der richtige Ort ist, um diesen Zweifel zu fragen, oder ich hätte eine neue Frage stellen sollen, aber ich habe einen ziemlich ähnlichen Zweifel.



void print(int n) {
  if (n < 0) return;
  cout << " " << n;
// The last executed statement is recursive call
  print(n-1);
  print(n-1);
}

Ist dieser Schwanz rekursiv?

Question 6

Die Schwanzrekursion ist die Optimierung moderner Compiler, die als Schwanz -Call -Eliminierung bezeichnet werden. Wenn die Anrufer-/übergeordnete Funktion nach Abschluss des Kindes nach Abschluss der Aufwicklungsstufen nichts erledigen muss, ist das letzte, was der Recursion -Ruf selbst selbst ist, der moderne Compiler verwendet die GOTO und die Beschriftungen für die Optimierung.

Beispiel: Unsere Version -> Drucke n bis 1

void fun(int n){
if(n==0)
return;
printf("%d\n",n);
fun(n-1)
}

nach Optimierung->

void fun(int n){
start:
if(n==0)
return;
printf("%d\n",n);
n=n-1;
goto start;
}

Vorteile dieser Optimierung: 1. Verhält nur sehr wenige Stapelrahmen für schwanzrezisive Aufrufe 2. Erzählt weniger Speicher 3.No muss den Verfahrensaktivierungsdatensatz speichern, dies verringert den Funktionsaufwand. 3. Nicht mehr Segmentierungsfehler ist C/C ++ und Stapelüberlauf in Java.