Ist die Rekursion jemals schneller als eine Schleife?

286

Ich weiß, dass Rekursion manchmal viel sauberer ist als Schleifen, und ich frage nichts darüber, wann ich Rekursion über Iteration verwenden soll. Ich weiß, dass es dazu bereits viele Fragen gibt.

Was ich frage ist, ist Rekursion immer schneller als eine Schleife? Mir scheint, Sie könnten eine Schleife immer verfeinern und schneller ausführen als eine rekursive Funktion, da die Schleife nicht ständig neue Stapelrahmen einrichtet.

Ich suche speziell nach einer schnelleren Rekursion in Anwendungen, in denen die Rekursion der richtige Weg ist, um mit den Daten umzugehen, z. B. in einigen Sortierfunktionen, in Binärbäumen usw.

Carson Myers
quelle
3
Manchmal dauert es Jahrhunderte, bis iterative Prozeduren oder Formeln in geschlossener Form für einige Rezidive auftauchen. Ich denke nur zu diesen Zeiten ist die Rekursion schneller :) lol
Pratik Deoghare
23
Wenn ich für mich selbst spreche, bevorzuge ich die Iteration. ;-)
Iterator
mögliches Duplikat der Rekursion oder Iteration?
Nawfal
@PratikDeoghare Nein, es geht nicht darum, einen völlig anderen Algorithmus zu wählen. Sie können eine rekursive Funktion jederzeit in eine identisch funktionierende Methode konvertieren, die eine Schleife verwendet. Zum Beispiel hat diese Antwort den gleichen Algorithmus sowohl rekursive und Looping - Format . Im Allgemeinen werden Sie ein Tupel der Argumente für die rekursive Funktion in einen Stapel einfügen, zum Aufrufen auf den Stapel drücken und vom Stapel verwerfen, um von der Funktion zurückzukehren.
TamaMcGlinn

Antworten:

356

Dies hängt von der verwendeten Sprache ab. Sie haben 'sprachunabhängig' geschrieben, deshalb gebe ich einige Beispiele.

In Java, C und Python ist die Rekursion im Vergleich zur Iteration (im Allgemeinen) ziemlich teuer, da ein neuer Stapelrahmen zugewiesen werden muss. In einigen C-Compilern kann ein Compiler-Flag verwendet werden, um diesen Overhead zu beseitigen, der bestimmte Arten von Rekursionen (tatsächlich bestimmte Arten von Tail-Aufrufen) in Sprünge anstelle von Funktionsaufrufen umwandelt.

In Implementierungen funktionaler Programmiersprachen kann die Iteration manchmal sehr teuer und die Rekursion sehr billig sein. In vielen Fällen wird die Rekursion in einen einfachen Sprung umgewandelt, aber das Ändern der Schleifenvariablen (die veränderbar ist) erfordert manchmal relativ schwere Operationen, insbesondere bei Implementierungen, die mehrere Ausführungsthreads unterstützen. In einigen dieser Umgebungen ist die Mutation aufgrund der Interaktion zwischen dem Mutator und dem Garbage Collector teuer, wenn beide gleichzeitig ausgeführt werden.

Ich weiß, dass in einigen Schema-Implementierungen die Rekursion im Allgemeinen schneller ist als die Schleife.

Kurz gesagt, die Antwort hängt vom Code und der Implementierung ab. Verwenden Sie einen beliebigen Stil. Wenn Sie eine funktionale Sprache verwenden, ist die Rekursion möglicherweise schneller. Wenn Sie eine imperative Sprache verwenden, ist die Iteration wahrscheinlich schneller. In einigen Umgebungen führen beide Methoden dazu, dass dieselbe Baugruppe generiert wird (legen Sie diese in Ihr Rohr und rauchen Sie sie).

Nachtrag: In einigen Umgebungen ist die beste Alternative weder Rekursion noch Iteration, sondern Funktionen höherer Ordnung. Dazu gehören "Map", "Filter" und "Reduce" (auch "Fold" genannt). Dies ist nicht nur der bevorzugte Stil, sondern auch häufig sauberer. In einigen Umgebungen sind diese Funktionen die ersten (oder einzigen), die durch die automatische Parallelisierung einen Schub erhalten. Sie können daher erheblich schneller sein als Iteration oder Rekursion. Data Parallel Haskell ist ein Beispiel für eine solche Umgebung.

Listenverständnisse sind eine weitere Alternative, aber dies sind normalerweise nur syntaktische Zucker für Iterations-, Rekursions- oder Funktionen höherer Ordnung.

Dietrich Epp
quelle
48
Ich +1 das und möchte kommentieren, dass "Rekursion" und "Schleifen" genau das sind, was Menschen ihren Code nennen. Entscheidend für die Leistung ist nicht, wie Sie Dinge benennen , sondern wie sie kompiliert / interpretiert werden. Rekursion ist per Definition ein mathematisches Konzept und hat wenig mit Stapelrahmen und Baugruppen zu tun.
P Shved
1
Außerdem ist die Rekursion in funktionalen Sprachen im Allgemeinen der natürlichere Ansatz, und die Iteration ist in imperativen Sprachen normalerweise intuitiver. Es ist unwahrscheinlich, dass sich der Leistungsunterschied bemerkbar macht. Verwenden Sie daher einfach das, was sich für diese bestimmte Sprache natürlicher anfühlt. Zum Beispiel möchten Sie wahrscheinlich keine Iteration in Haskell verwenden, wenn die Rekursion viel einfacher ist.
Sasha Chedygov
4
Im Allgemeinen wird die Rekursion zu Schleifen kompiliert , wobei Schleifen ein Konstrukt niedrigerer Ebene sind. Warum? Da die Rekursion in der Regel über eine bestimmte Datenstruktur gut begründet ist, können Sie eine anfängliche F-Algebra induzieren und einige Eigenschaften der Terminierung sowie induktive Argumente zur Struktur der (rekursiven) Berechnung nachweisen. Der Prozess, mit dem die Rekursion zu Schleifen kompiliert wird, ist die Tail-Call-Optimierung.
Kristopher Micinski
Am wichtigsten sind nicht ausgeführte Operationen. Je mehr Sie "IO", desto mehr müssen Sie verarbeiten. Das Aufheben der E / A-Daten (auch als Indizierung bezeichnet) ist immer die größte Leistungssteigerung für jedes System, da Sie diese nicht erst verarbeiten müssen.
Jeff Fischer
53

Ist die Rekursion immer schneller als eine Schleife?

Nein, die Iteration ist immer schneller als die Rekursion. (in einer Von Neumann-Architektur)

Erläuterung:

Wenn Sie die Mindestoperationen eines generischen Computers von Grund auf neu erstellen, steht "Iteration" an erster Stelle als Baustein und ist weniger ressourcenintensiv als "Rekursion". Daher ist ergo schneller.

Eine Pseudo-Computer-Maschine von Grund auf neu bauen:

Frage dich : Was brauchst du, um einen Wert zu berechnen , dh um einem Algorithmus zu folgen und ein Ergebnis zu erzielen?

Wir werden eine Hierarchie von Konzepten erstellen, beginnend bei Null und zunächst die grundlegenden Kernkonzepte definieren und dann mit diesen Konzepte der zweiten Ebene erstellen und so weiter.

  1. Erstes Konzept: Speicherzellen, Speicher, Status . Um etwas zu tun, benötigen Sie Orte zum Speichern der endgültigen und mittleren Ergebniswerte. Nehmen wir an, wir haben ein unendliches Array von "ganzzahligen" Zellen, genannt Speicher , M [0..Infinite].

  2. Anleitung: etwas tun - eine Zelle transformieren, ihren Wert ändern. Zustand ändern . Jede interessante Anweisung führt eine Transformation durch. Grundlegende Anweisungen sind:

    a) Speicherzellen setzen und verschieben

    • Speichern Sie einen Wert im Speicher, z. B.: Speichern Sie 5 m [4]
    • Kopieren Sie einen Wert an eine andere Position: zB: speichern Sie m [4] m [8]

    b) Logik und Arithmetik

    • und oder xor nicht
    • add, sub, mul, div. zB m [7] m [8] hinzufügen
  3. Ein ausführender Agent : ein Kern in einer modernen CPU. Ein "Agent" kann Anweisungen ausführen. Ein Agent kann auch eine Person sein, die dem Algorithmus auf Papier folgt.

  4. Reihenfolge der Schritte: eine Folge von Anweisungen : dh: zuerst ausführen, danach tun usw. Eine zwingende Folge von Anweisungen. Sogar einzeilige Ausdrücke sind "eine zwingende Folge von Anweisungen". Wenn Sie einen Ausdruck mit einer bestimmten "Bewertungsreihenfolge" haben, haben Sie Schritte . Dies bedeutet, dass selbst ein einzelner zusammengesetzter Ausdruck implizite „Schritte“ und eine implizite lokale Variable enthält (nennen wir ihn „Ergebnis“). z.B:

    4 + 3 * 2 - 5
    (- (+ (* 3 2) 4 ) 5)
    (sub (add (mul 3 2) 4 ) 5)  
    

    Der obige Ausdruck impliziert 3 Schritte mit einer impliziten "Ergebnis" -Variablen.

    // pseudocode
    
           1. result = (mul 3 2)
           2. result = (add 4 result)
           3. result = (sub result 5)
    

    Selbst Infix-Ausdrücke sind daher eine zwingende Folge von Anweisungen , da Sie eine bestimmte Auswertungsreihenfolge haben . Der Ausdruck impliziert eine Folge von Operationen, die in einer bestimmten Reihenfolge ausgeführt werden müssen, und da es Schritte gibt, gibt es auch eine implizite Zwischenvariable "Ergebnis".

  5. Anweisungszeiger : Wenn Sie eine Folge von Schritten haben, haben Sie auch einen impliziten "Anweisungszeiger". Der Befehlszeiger markiert den nächsten Befehl und rückt vor, nachdem der Befehl gelesen wurde, aber bevor der Befehl ausgeführt wird.

    In dieser Pseudo-Rechenmaschine ist der Befehlszeiger Teil des Speichers . (Hinweis: Normalerweise ist der Befehlszeiger ein "spezielles Register" in einem CPU-Kern, aber hier werden wir die Konzepte vereinfachen und davon ausgehen, dass alle Daten (einschließlich Register) Teil von "Speicher" sind.)

  6. Springen - Sobald Sie eine geordnete Anzahl von Schritten und einen Anweisungszeiger haben , können Sie die Anweisung " Speichern " anwenden , um den Wert des Anweisungszeigers selbst zu ändern. Wir werden diese spezielle Verwendung der Speicheranweisung mit einem neuen Namen bezeichnen: Jump . Wir verwenden einen neuen Namen, weil es einfacher ist, ihn als neues Konzept zu betrachten. Durch Ändern des Anweisungszeigers weisen wir den Agenten an, „mit Schritt x fortzufahren“.

  7. Unendliche Iteration : Durch Zurückspringen können Sie den Agenten jetzt dazu bringen, eine bestimmte Anzahl von Schritten zu "wiederholen". Zu diesem Zeitpunkt haben wir eine unendliche Iteration.

                       1. mov 1000 m[30]
                       2. sub m[30] 1
                       3. jmp-to 2  // infinite loop
    
  8. Bedingt - Bedingte Ausführung von Anweisungen. Mit der "bedingten" Klausel können Sie eine von mehreren Anweisungen basierend auf dem aktuellen Status (der mit einer vorherigen Anweisung festgelegt werden kann) bedingt ausführen.

  9. Richtige Iteration : Mit der Bedingungsklausel können wir nun der Endlosschleife der Rücksprunganweisung entkommen . Wir haben jetzt eine bedingte Schleife und dann die richtige Iteration

    1. mov 1000 m[30]
    2. sub m[30] 1
    3. (if not-zero) jump 2  // jump only if the previous 
                            // sub instruction did not result in 0
    
    // this loop will be repeated 1000 times
    // here we have proper ***iteration***, a conditional loop.
    
  10. Benennen : Geben Sie einem bestimmten Speicherort Namen, der Daten oder einen Schritt enthält . Dies ist nur eine "Bequemlichkeit" zu haben. Wir fügen keine neuen Anweisungen hinzu, indem wir "Namen" für Speicherorte definieren können. "Benennen" ist keine Anweisung für den Agenten, sondern nur eine Annehmlichkeit für uns. Durch die Benennung ist Code (an dieser Stelle) leichter zu lesen und leichter zu ändern.

       #define counter m[30]   // name a memory location
       mov 1000 counter
    loop:                      // name a instruction pointer location
        sub counter 1
        (if not-zero) jmp-to loop  
    
  11. Einstufiges Unterprogramm : Angenommen, Sie müssen eine Reihe von Schritten häufig ausführen. Sie können die Schritte an einer benannten Position im Speicher speichern und dann zu dieser Position springen , wenn Sie sie ausführen müssen (Aufruf). Am Ende der Sequenz werden Sie brauchen Rückkehr zum Punkt des Aufrufs Ausführung fortzusetzen. Mit diesem Mechanismus erstellen Sie neue Anweisungen (Unterprogramme), indem Sie Kernanweisungen erstellen .

    Implementierung: (keine neuen Konzepte erforderlich)

    • Speichern Sie den aktuellen Anweisungszeiger an einer vordefinierten Speicherposition
    • zum Unterprogramm springen
    • Am Ende der Unterroutine rufen Sie den Anweisungszeiger aus dem vordefinierten Speicherort ab und springen effektiv zur folgenden Anweisung des ursprünglichen Aufrufs zurück

    Problem mit der einstufigen Implementierung: Sie können keine andere Unterroutine von einer Unterroutine aus aufrufen. In diesem Fall überschreiben Sie die Rücksprungadresse (globale Variable), sodass Sie keine Anrufe verschachteln können.

    Um eine bessere Implementierung für Unterprogramme zu haben: Sie benötigen einen STACK

  12. Stapel : Sie definieren einen Speicherplatz als "Stapel", Sie können Werte auf dem Stapel "pushen" und auch den letzten "gepussten" Wert "platzen". Um einen Stapel zu implementieren Sie benötigen Stapelzeiger (ähnlich dem Instruction Pointer) , die Punkte auf den tatsächlichen „Kopf“ des Stapels. Wenn Sie einen Wert „pushen“, wird der Stapelzeiger dekrementiert und Sie speichern den Wert. Wenn Sie "pop", erhalten Sie den Wert am tatsächlichen Stapelzeiger und dann wird der Stapelzeiger erhöht.

  13. Unterprogramme Jetzt, da wir einen Stapel haben, können wir geeignete Unterprogramme implementieren, die verschachtelte Aufrufe ermöglichen . Die Implementierung ist ähnlich, aber anstatt den Befehlszeiger an einer vordefinierten Speicherposition zu speichern, "pushen" wir den Wert der IP im Stapel . Am Ende der Unterroutine „platzen“ wir einfach den Wert vom Stapel und springen nach dem ursprünglichen Aufruf effektiv zur Anweisung zurück . Diese Implementierung mit einem „Stapel“ ermöglicht das Aufrufen einer Unterroutine von einer anderen Unterroutine. Mit dieser Implementierung können wir mehrere Abstraktionsebenen erstellen, wenn wir neue Anweisungen als Unterroutinen definieren, indem wir Kernanweisungen oder andere Unterroutinen als Bausteine ​​verwenden.

  14. Rekursion : Was passiert, wenn sich ein Unterprogramm selbst aufruft? Dies wird als "Rekursion" bezeichnet.

    Problem: Überschreiben der lokalen Zwischenergebnisse, die eine Unterroutine im Speicher speichern kann. Da Sie dieselben Schritte aufrufen / wiederverwenden, werden die Zwischenergebnisse , wenn sie an vordefinierten Speicherorten (globalen Variablen) gespeichert sind, bei den verschachtelten Aufrufen überschrieben.

    Lösung: Um eine Rekursion zu ermöglichen, sollten Unterprogramme lokale Zwischenergebnisse im Stapel speichern. Daher werden die Zwischenergebnisse bei jedem rekursiven Aufruf (direkt oder indirekt) an verschiedenen Speicherorten gespeichert.

...

Nachdem wir die Rekursion erreicht haben, hören wir hier auf.

Fazit:

In einer Von Neumann-Architektur ist "Iteration" eindeutig ein einfacheres / grundlegendes Konzept als "Rekursion" . Wir haben eine Form der "Iteration" auf Ebene 7, während "Rekursion" auf Ebene 14 der Konzepthierarchie ist.

Die Iteration im Maschinencode ist immer schneller, da weniger Anweisungen und damit weniger CPU-Zyklen erforderlich sind.

Welches ist besser"?

  • Sie sollten "Iteration" verwenden, wenn Sie einfache, sequentielle Datenstrukturen verarbeiten, und überall dort, wo eine "einfache Schleife" ausreicht.

  • Sie sollten "Rekursion" verwenden, wenn Sie eine rekursive Datenstruktur verarbeiten müssen (ich nenne sie gerne "Fraktale Datenstrukturen") oder wenn die rekursive Lösung deutlich "eleganter" ist.

Tipp : Verwenden Sie das beste Werkzeug für den Job, aber verstehen Sie das Innenleben jedes Werkzeugs, um mit Bedacht zu wählen.

Beachten Sie schließlich, dass Sie viele Möglichkeiten haben, die Rekursion zu verwenden. Sie haben überall rekursive Datenstrukturen , Sie sehen sich jetzt eine an: Teile des DOM, die das unterstützen, was Sie lesen, sind ein RDS, ein JSON-Ausdruck ist ein RDS, das hierarchische Dateisystem in Ihrem Computer ist ein RDS, dh: Sie haben ein Stammverzeichnis, das Dateien und Verzeichnisse enthält, jedes Verzeichnis, das Dateien und Verzeichnisse enthält, jedes dieser Verzeichnisse, das Dateien und Verzeichnisse enthält ...

Lucio M. Tato
quelle
2
Sie gehen davon aus, dass Ihr Fortschritt 1) ​​notwendig ist und 2) dass er dort aufhört, wo Sie es getan haben. Aber 1) es ist nicht notwendig (zum Beispiel kann Rekursion in einen Sprung verwandelt werden, wie die akzeptierte Antwort erklärt, so dass kein Stapel benötigt wird), und 2) es muss dort nicht aufhören (zum Beispiel irgendwann Sie Sie erreichen eine gleichzeitige Verarbeitung, die möglicherweise Sperren erfordert, wenn Sie einen veränderlichen Status haben, wie Sie ihn in Ihrem zweiten Schritt eingeführt haben, sodass alles langsamer wird. Eine unveränderliche Lösung wie eine funktionale / rekursive würde das Sperren vermeiden und könnte daher schneller / paralleler sein. .
Hmijail trauert um Rücktritte
2
"Rekursion kann in einen Sprung verwandelt werden" ist falsch. Wirklich nützliche Rekursion kann nicht in einen Sprung verwandelt werden. Der Tail-Aufruf "Rekursion" ist ein Sonderfall, bei dem Sie "als Rekursion" codieren, was vom Compiler in eine Schleife vereinfacht werden kann. Außerdem verbinden Sie "unveränderlich" mit "Rekursion", das sind orthogonale Konzepte.
Lucio M. Tato
"Wirklich nützliche Rekursion kann nicht in einen Sprung verwandelt werden" -> also ist die Tail-Call-Optimierung irgendwie nutzlos? Auch unveränderlich und rekursiv mögen orthogonal sein, aber Sie verknüpfen Schleifen mit veränderlichen Zählern - sehen Sie sich Schritt 9 an. Mir scheint, Sie denken, dass Schleifen und Rekursion radikal unterschiedliche Konzepte sind. sie sind nicht. stackoverflow.com/questions/2651112/…
hmijail trauert um den 30.
@hmijail Ich denke, dass ein besseres Wort als "nützlich" "wahr" ist. Die Schwanzrekursion ist keine echte Rekursion, da nur die Funktionsaufrufsyntax verwendet wird, um die bedingungslose Verzweigung, dh die Iteration, zu verschleiern. Durch echte Rekursion erhalten wir einen Backtracking-Stapel. Die Schwanzrekursion ist jedoch immer noch ausdrucksstark, was sie nützlich macht. Die Eigenschaften der Rekursion, die es einfach oder einfacher machen, Code auf Richtigkeit zu analysieren, werden iterativem Code übertragen, wenn er mithilfe von Tail-Aufrufen ausgedrückt wird. Dies wird jedoch manchmal durch zusätzliche Komplikationen in der Heckversion wie zusätzliche Parameter leicht ausgeglichen.
Kaz
34

Die Rekursion kann schneller sein, wenn die Alternative darin besteht, einen Stapel explizit zu verwalten, wie in den von Ihnen erwähnten Sortier- oder Binärbaumalgorithmen.

Ich hatte einen Fall, in dem das Umschreiben eines rekursiven Algorithmus in Java langsamer wurde.

Der richtige Ansatz besteht also darin, es zuerst auf natürlichste Weise zu schreiben, nur zu optimieren, wenn die Profilerstellung zeigt, dass es kritisch ist, und dann die vermeintliche Verbesserung zu messen.

Sternenblau
quelle
2
+1 für " Schreiben Sie es zuerst auf natürlichste Weise " und insbesondere " Nur optimieren, wenn die Profilerstellung zeigt, dass es kritisch ist "
TripeHound
2
+1 für die Bestätigung, dass der Hardware-Stack möglicherweise schneller ist als ein manuell implementierter Software-In-Heap-Stack. Effektiv zeigen, dass alle "Nein" -Antworten falsch sind.
sh1
12

Die Schwanzrekursion ist so schnell wie eine Schleife. In vielen funktionalen Sprachen ist eine Schwanzrekursion implementiert.

mkorpela
quelle
35
Die Schwanzrekursion kann so schnell wie eine Schleife sein, wenn eine Schwanzaufrufoptimierung implementiert ist: c2.com/cgi/wiki?TailCallOptimization
Joachim Sauer
12

Überlegen Sie, was für jede Iteration und Rekursion unbedingt zu tun ist.

  • Iteration: Ein Sprung zum Anfang der Schleife
  • Rekursion: Ein Sprung zum Anfang der aufgerufenen Funktion

Sie sehen, dass hier nicht viel Raum für Unterschiede ist.

(Ich gehe davon aus, dass Rekursion ein Tail-Call ist und der Compiler sich dieser Optimierung bewusst ist.)

Pasi Savolainen
quelle
9

Die meisten Antworten hier vergessen den offensichtlichen Schuldigen, warum die Rekursion oft langsamer ist als iterative Lösungen. Es ist mit dem Auf- und Abbau von Stapelrahmen verbunden, aber nicht genau das. Es ist im Allgemeinen ein großer Unterschied in der Speicherung der automatischen Variablen für jede Rekursion. In einem iterativen Algorithmus mit einer Schleife werden die Variablen häufig in Registern gespeichert, und selbst wenn sie verschüttet werden, befinden sie sich im Level 1-Cache. In einem rekursiven Algorithmus werden alle Zwischenzustände der Variablen auf dem Stapel gespeichert, was bedeutet, dass sie viel mehr Speicherverluste verursachen. Dies bedeutet, dass selbst wenn es die gleiche Anzahl von Operationen ausführt, es viele Speicherzugriffe in der Hot-Loop gibt und was diese Sache noch schlimmer macht, diese Speicheroperationen eine miese Wiederverwendungsrate haben, die die Caches weniger effektiv macht.

Rekursive TL; DR-Algorithmen weisen im Allgemeinen ein schlechteres Cache-Verhalten auf als iterative.

Patrick Schlüter
quelle
6

Die meisten Antworten hier sind falsch . Die richtige Antwort ist, es kommt darauf an . Hier sind zum Beispiel zwei C-Funktionen, die durch einen Baum gehen. Zuerst die rekursive:

static
void mm_scan_black(mm_rc *m, ptr p) {
    SET_COL(p, COL_BLACK);
    P_FOR_EACH_CHILD(p, {
        INC_RC(p_child);
        if (GET_COL(p_child) != COL_BLACK) {
            mm_scan_black(m, p_child);
        }
    });
}

Und hier ist dieselbe Funktion, die mithilfe der Iteration implementiert wurde:

static
void mm_scan_black(mm_rc *m, ptr p) {
    stack *st = m->black_stack;
    SET_COL(p, COL_BLACK);
    st_push(st, p);
    while (st->used != 0) {
        p = st_pop(st);
        P_FOR_EACH_CHILD(p, {
            INC_RC(p_child);
            if (GET_COL(p_child) != COL_BLACK) {
                SET_COL(p_child, COL_BLACK);
                st_push(st, p_child);
            }
        });
    }
}

Es ist nicht wichtig, die Details des Codes zu verstehen. Nur das psind Knoten und das P_FOR_EACH_CHILDmacht das Gehen. In der iterativen Version benötigen wir einen expliziten Stapel, stauf den Knoten geschoben und dann gepoppt und manipuliert werden.

Die rekursive Funktion läuft viel schneller als die iterative. Der Grund ist, dass in letzterem für jedes Element ein CALLzu der Funktion st_pushbenötigt wird und dann ein anderes zu st_pop.

Im ersteren haben Sie nur die Rekursive CALLfür jeden Knoten.

Außerdem ist der Zugriff auf Variablen im Callstack unglaublich schnell. Dies bedeutet, dass Sie aus dem Speicher lesen, der sich wahrscheinlich immer im innersten Cache befindet. Ein expliziter Stapel muss dagegen durch malloc: ed-Speicher vom Heap gesichert werden, auf den viel langsamer zugegriffen werden kann.

Durch sorgfältige Optimierung wie Inlining st_pushund st_popkann ich ungefähr die Parität mit dem rekursiven Ansatz erreichen. Aber zumindest auf meinem Computer sind die Kosten für den Zugriff auf den Heap-Speicher höher als die Kosten für den rekursiven Aufruf.

Diese Diskussion ist jedoch meistens umstritten, da rekursives Baumlaufen nicht korrekt ist . Wenn Sie einen ausreichend großen Baum haben, wird Ihnen der Callstack-Speicherplatz ausgehen, weshalb ein iterativer Algorithmus verwendet werden muss.

Björn Lindqvist
quelle
Ich kann bestätigen, dass ich in eine ähnliche Situation geraten bin und dass es Situationen gibt, in denen die Rekursion schneller sein kann als ein manueller Stapel auf dem Heap. Insbesondere, wenn die Optimierung im Compiler aktiviert ist, um den Aufwand für den Aufruf einer Funktion zu vermeiden.
while1fork
1
10 ^ 8-mal einen 7-Knoten-Binärbaum vorbestellt. Rekursion 25ns. Expliziter Stapel (gebunden oder nicht - macht keinen großen Unterschied) ~ 15ns. Die Rekursion muss mehr tun (Speichern und Wiederherstellen von Registern + (normalerweise) strengere Rahmenausrichtungen) als nur schieben und springen. (Und es wird schlimmer mit PLT in dynamisch verknüpften Bibliotheken.) Sie müssen den expliziten Stapel nicht auf einem Heap zuordnen. Sie können ein Hindernis ausführen, dessen erster Frame sich auf dem regulären Aufrufstapel befindet, damit Sie die Cache-Lokalität nicht für den häufigsten Fall opfern, in dem Sie den ersten Block nicht überschreiten.
PSkocik
3

Nein, Rekursion ist im Allgemeinen nicht schneller als eine Schleife in einer realistischen Verwendung, die in beiden Formen praktikable Implementierungen aufweist. Ich meine, sicher, Sie könnten Schleifen codieren, die ewig dauern, aber es gibt bessere Möglichkeiten, dieselbe Schleife zu implementieren, die jede Implementierung desselben Problems durch Rekursion übertreffen könnte.

Sie haben den Nagel auf den Kopf getroffen, was den Grund betrifft. Das Erstellen und Zerstören von Stapelrahmen ist teurer als ein einfacher Sprung.

Beachten Sie jedoch, dass ich sagte, "hat tragfähige Implementierungen in beiden Formen". Für Dinge wie viele Sortieralgorithmen gibt es in der Regel keine sehr praktikable Methode, um sie zu implementieren, bei der eine eigene Version eines Stapels nicht effektiv eingerichtet wird, da untergeordnete "Aufgaben" erzeugt werden, die von Natur aus Teil des Prozesses sind. Daher kann die Rekursion genauso schnell sein wie der Versuch, den Algorithmus über eine Schleife zu implementieren.

Bearbeiten: Diese Antwort setzt nicht funktionierende Sprachen voraus, in denen die meisten grundlegenden Datentypen veränderbar sind. Es gilt nicht für funktionale Sprachen.

Bernstein
quelle
Aus diesem Grund werden mehrere Rekursionsfälle häufig von Compilern in Sprachen optimiert, in denen häufig Rekursionen verwendet werden. In F # sehen Sie beispielsweise zusätzlich zur vollständigen Unterstützung rekursiver Funktionen mit dem .tail-Opcode häufig eine rekursive Funktion, die als Schleife kompiliert wurde.
Em70
Ja. Die Schwanzrekursion kann manchmal das Beste aus beiden Welten sein - die funktional "angemessene" Art, eine rekursive Aufgabe zu implementieren, und die Leistung der Verwendung einer Schleife.
Amber
1
Dies ist im Allgemeinen nicht korrekt. In einigen Umgebungen ist eine Mutation (die mit GC interagiert) teurer als eine Schwanzrekursion, die in der Ausgabe in eine einfachere Schleife umgewandelt wird, die keinen zusätzlichen Stapelrahmen verwendet.
Dietrich Epp
2

Nein, in jedem realistischen System ist das Erstellen eines Stapelrahmens immer teurer als ein INC und ein JMP. Aus diesem Grund wandeln wirklich gute Compiler die Schwanzrekursion automatisch in einen Aufruf desselben Frames um, dh ohne Overhead, sodass Sie die besser lesbare Quellversion und die effizientere kompilierte Version erhalten. Ein wirklich sehr guter Compiler sollte sogar in der Lage sein, normale Rekursion in Schwanzrekursion umzuwandeln, wo dies möglich ist.

Kilian Foth
quelle
1

Bei der funktionalen Programmierung geht es mehr um " was " als um " wie ".

Die Sprachimplementierer werden einen Weg finden, die Funktionsweise des Codes darunter zu optimieren, wenn wir nicht versuchen, ihn optimierter zu gestalten, als er sein muss. Die Rekursion kann auch in den Sprachen optimiert werden, die die Tail-Call-Optimierung unterstützen.

Aus Sicht des Programmierers ist die Lesbarkeit und Wartbarkeit wichtiger als die Optimierung. Wiederum ist "vorzeitige Optimierung die Wurzel allen Übels".

noego
quelle
0

Dies ist eine Vermutung. Im Allgemeinen schlägt die Rekursion bei Problemen mit anständiger Größe wahrscheinlich nicht oft oder nie die Schleife, wenn beide wirklich gute Algorithmen verwenden (ohne Implementierungsschwierigkeiten). Sie kann unterschiedlich sein, wenn sie mit einer Sprache mit Tail-Call-Rekursion (und einem Tail- Rekursionsalgorithmus) verwendet wird und mit Schleifen auch als Teil der Sprache) - die wahrscheinlich sehr ähnlich wären und möglicherweise manchmal sogar eine Rekursion bevorzugen würden.

Roman A. Taycher
quelle
0

Nach der Theorie sind es die gleichen Dinge. Rekursion und Schleife mit derselben O () -Komplexität funktionieren mit derselben theoretischen Geschwindigkeit, aber die tatsächliche Geschwindigkeit hängt natürlich von Sprache, Compiler und Prozessor ab. Beispiel mit Potenz der Zahl kann iterativ mit O (ln (n)) codiert werden:

  int power(int t, int k) {
  int res = 1;
  while (k) {
    if (k & 1) res *= t;
    t *= t;
    k >>= 1;
  }
  return res;
  }
Hydrophis Spiralis
quelle
1
Big O ist "proportional zu". Beides ist es also O(n), aber eines kannx für alle mal länger dauern als das andere n.
Strg-Alt-Delor