Ist eine Rekursion jemals schneller als eine Schleife?

Question

Ich weiß, dass die Rekursion manchmal viel sauberer ist als eine Schleife, und ich frage nicht, wann ich die Rekursion über die Iteration verwenden sollte, ich weiß, dass es bereits viele Fragen dazu gibt.

Meine Frage ist: Ist Rekursion immer schneller als eine Schleife? Mir scheint, dass man eine Schleife immer verfeinern und schneller ausführen kann als eine rekursive Funktion, weil die Schleife nicht ständig neue Stackframes aufbaut.

Ich bin speziell auf der Suche danach, ob die Rekursion in Anwendungen schneller ist, in denen die Rekursion der richtige Weg ist, um die Daten zu verarbeiten, wie z. B. in einigen Sortierfunktionen, in binären Bäumen, usw.

Answer 1

Dies hängt von der verwendeten Sprache ab. Sie schrieben "sprachunabhängig", also werde ich einige Beispiele nennen.

In Java, C und Python ist die Rekursion im Vergleich zur Iteration (im Allgemeinen) ziemlich teuer, da sie die Zuweisung eines neuen Stack Frames erfordert. In einigen C-Compilern kann man ein Compiler-Flag verwenden, um diesen Overhead zu eliminieren, wodurch bestimmte Arten von Rekursionen (eigentlich bestimmte Arten von Tail-Calls) in Sprünge statt in Funktionsaufrufe umgewandelt werden.

In den Implementierungen funktionaler Programmiersprachen kann Iteration manchmal sehr teuer und Rekursion sehr billig sein. In vielen Fällen wird die Rekursion in einen einfachen Sprung umgewandelt, aber die Änderung der Schleifenvariablen (die veränderbar ist) manchmal erfordert einige relativ schwerfällige Operationen, insbesondere bei Implementierungen, die mehrere Threads zur Ausführung unterstützen. Die Mutation ist in einigen dieser Umgebungen aufgrund der Interaktion zwischen dem Mutator und dem Garbage Collector teuer, wenn beide gleichzeitig ausgeführt werden können.

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

Kurz gesagt, die Antwort hängt vom Code und der Implementierung ab. Verwenden Sie den von Ihnen bevorzugten Stil. Wenn Sie eine funktionale Sprache verwenden, ist Rekursion puede schneller sein. Wenn Sie eine imperative Sprache verwenden, ist Iteration wahrscheinlich schneller. In manchen Umgebungen führen beide Methoden dazu, dass dieselbe Baugruppe erstellt wird (stecken Sie das in Ihre Pfeife und rauchen Sie es).

Nachtrag: In manchen Umgebungen sind weder Rekursion noch Iteration die beste Alternative, sondern Funktionen höherer Ordnung. Dazu gehören "map", "filter" und "reduce" (auch "fold" genannt). Diese sind nicht nur die bevorzugte Art, sie sind auch oft sauberer, und in manchen Umgebungen sind diese Funktionen die ersten (oder einzigen), die von der automatischen Parallelisierung profitieren - sie können also deutlich schneller sein als Iteration oder Rekursion. Data Parallel Haskell ist ein Beispiel für eine solche Umgebung.

List comprehensions sind eine weitere Alternative, aber diese sind in der Regel nur syntaktischer Zucker für Iteration, Rekursion oder Funktionen höherer Ordnung.

Answer 2

Ist eine Rekursion jemals schneller als eine Schleife?

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

Erläuterung:

Wenn man die minimalen Operationen eines generischen Computers von Grund auf neu aufbaut, steht "Iteration" als Baustein an erster Stelle und ist weniger ressourcenintensiv als "Rekursion", ergo schneller.

Bau einer Pseudo-Computer-Maschine von Grund auf:

Fragen Sie sich selbst : Was müssen Sie tun? berechnen Sie einen Wert, d.h. einem Algorithmus zu folgen und ein Ergebnis zu erzielen?

Wir werden eine Hierarchie von Konzepten aufstellen, indem wir bei Null anfangen und zunächst die grundlegenden, zentralen Konzepte definieren, dann Konzepte der zweiten Ebene mit diesen aufbauen und so weiter.

1. Erstes Konzept: Speicherzellen, Speicherung, Zustand . Um etwas zu tun, müssen Sie Orte um End- und Zwischenergebniswerte zu speichern. Nehmen wir an, wir haben eine unendliche Reihe von "Integer"-Zellen, genannt Speicher , M[0..Unendlich].

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

   a) Speicherzellen setzen und verschieben

   • einen Wert im Speicher speichern, z.B.: 5 m[4] speichern
   • einen Wert an eine andere Stelle kopieren: z.B.: speichern m[4] m[8]

   b) Logik und Arithmetik

   • und, oder, xor, nicht
   • add, sub, mul, div. z.B. hinzufügen m[7] m[8]

3. Ein Vollstreckungsorgan : a Kernstück in einer modernen CPU. Ein "Agent" ist etwas, das Anweisungen ausführen kann. Ein Agent kann auch eine Person sein, die dem Algorithmus auf dem Papier folgt.

4. Reihenfolge der Schritte: eine Abfolge von Anweisungen d.h.: erst dies, dann das usw. Eine imperative Folge von Anweisungen. Auch eine Zeile Ausdrücke sind "eine imperative Folge von Anweisungen". Wenn Sie einen Ausdruck mit einer bestimmten "Auswertungsreihenfolge" haben, dann haben Sie Schritte . Das bedeutet, dass sogar ein einzelner zusammengesetzter Ausdruck implizite "Schritte" hat und auch eine implizite lokale Variable (nennen wir sie "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)

   Da Sie eine bestimmte Auswertungsreihenfolge haben, sind sogar Infix-Ausdrücke eine imperative Folge von Anweisungen . Der Ausdruck impliziert eine Folge von Vorgängen, die in einer bestimmten Reihenfolge auszuführen sind, und weil es Schritte gibt es auch eine implizite Zwischenvariable "Ergebnis".

5. Anweisung Zeiger : Wenn Sie eine Folge von Schritten haben, haben Sie auch einen impliziten "Anweisungszeiger". Der Anweisungszeiger markiert die nächste Anweisung und rückt vor, nachdem die Anweisung gelesen wurde, aber bevor sie ausgeführt wird.

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

6. Springen - Sobald Sie eine geordnete Anzahl von Schritten und eine Anweisung Zeiger können Sie die " speichern "Anweisung, um den Wert des Anweisungszeigers selbst zu ändern. Wir nennen diese spezielle Verwendung des Speicherbefehl mit einem neuen Namen: Springen . Wir verwenden einen neuen Namen, weil es einfacher ist, es als neues Konzept zu betrachten. Indem wir den Anweisungszeiger ändern, weisen wir den Agenten an, "zum Schritt x zu gehen".

7. Unendliche Iteration : Durch zurückspringen, Jetzt können Sie den Agenten eine bestimmte Anzahl von Schritten "wiederholen" lassen. An diesem Punkt haben wir 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 "Conditional"-Klausel können Sie eine von mehreren Anweisungen abhängig vom aktuellen Zustand (der mit einer vorherigen Anweisung festgelegt werden kann) bedingt ausführen.

9. Richtige Iteration : Jetzt mit dem Bedingt Klausel können wir die Endlosschleife der zurückspringen Anweisung. Wir haben jetzt eine bedingte Schleife und dann 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. Namensgebung : Benennung eines bestimmten Speicherplatzes, der Daten enthält oder in dem ein Schritt . Dies ist nur eine "Bequemlichkeit" zu haben. Wir fügen keine neuen Anweisungen hinzu, indem wir die Möglichkeit haben, "Namen" für Speicherplätze zu definieren. Die "Benennung" ist keine Anweisung für den Agenten, sie ist nur eine Annehmlichkeit für uns. Namensgebung macht den Code (zu diesem Zeitpunkt) leichter lesbar und einfacher 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, es gibt eine Reihe von Schritten, die Sie häufig ausführen müssen. Sie können die Schritte an einer bestimmten Stelle im Speicher ablegen und dann Sprung zu diese Position, wenn Sie sie ausführen müssen (Aufruf). Am Ende der Sequenz müssen Sie return bis zu dem Punkt, an dem aufrufen um die Ausführung fortzusetzen. Mit diesem Mechanismus sind Sie Erstellung neuer Anweisungen (Unterprogramme) durch Zusammenstellung von Kernbefehlen.

    Umsetzung: (keine neuen Konzepte erforderlich)

    • Speichern des aktuellen Instruktionszeigers an einer vordefinierten Speicherposition
    • springen an das Unterprogramm
    • am Ende des Unterprogramms holen Sie den Anweisungszeiger von der vordefinierten Speicherstelle ab und springen damit zur folgenden Anweisung des ursprünglichen Programms zurück aufrufen

    Problem mit dem eine Ebene Umsetzung: Sie können kein anderes Unterprogramm aus einem Unterprogramm heraus aufrufen. Wenn Sie dies tun, überschreiben Sie die Rücksprungadresse (globale Variable), so dass Sie keine Aufrufe verschachteln können.

    Um eine Bessere Implementierung für Unterroutinen: Sie benötigen einen STACK

12. Stapel : Sie definieren einen Speicherbereich, der als "Stack" fungiert, Sie können Werte auf den Stack "schieben" und den letzten "geschobenen" Wert wieder "löschen". Um einen Stack zu implementieren, benötigen Sie eine Stapelzeiger (ähnlich wie der Befehlszeiger), der auf den eigentlichen "Kopf" des Stapels zeigt. Wenn Sie einen Wert "schieben", wird der Stapelzeiger dekrementiert und Sie speichern den Wert. Beim "Pop" wird der Wert am aktuellen Stapelzeiger abgeholt und der Stapelzeiger erhöht.

13. Unterroutinen Jetzt, wo wir eine Stapel können wir geeignete Unterprogramme implementieren Ermöglichung verschachtelter Aufrufe . Die Implementierung ist ähnlich, aber anstatt den Anweisungszeiger an einer vordefinierten Speicherposition zu speichern, "schieben" wir den Wert des IP in den Stapel . Am Ende des Unterprogramms wird der Wert einfach vom Stapel gepoppt, d.h. es wird zu der Anweisung zurückgesprungen, die auf die ursprüngliche Anweisung folgt aufrufen . Diese Implementierung mit einem "Stack" ermöglicht den Aufruf eines Unterprogramms von einem anderen Unterprogramm aus. Mit dieser Implementierung können wir bei der Definition mehrere Abstraktionsebenen schaffen neue Anweisungen als Unterprogramme, indem sie Kernbefehle oder andere Unterprogramme als Bausteine verwenden.

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

    Problem: Durch Überschreiben der lokalen Zwischenergebnisse kann ein Unterprogramm im Speicher abgelegt werden. Da Sie die gleichen Schritte aufrufen/wiederholen, si die Zwischenergebnisse in vordefinierten Speicherplätzen (globalen Variablen) gespeichert sind, werden sie bei den verschachtelten Aufrufen überschrieben.

    Lösung: Um eine Rekursion zu ermöglichen, sollten Unterprogramme lokale Zwischenergebnisse speichern auf dem Stapel daher bei jedem rekursiver Aufruf (direkt oder indirekt) werden die Zwischenergebnisse an verschiedenen Speicherplätzen abgelegt.

...

nach Erreichen Rekursion halten wir hier an.

Schlussfolgerung:

In einer Von-Neumann-Architektur, klar "Iteration" ist ein einfacheres/grundlegenderes Konzept als "Rekursion" . Wir haben eine Form von "Iteration" auf Stufe 7, während "Rekursion" befindet sich auf Ebene 14 der Begriffshierarchie.

Iteration wird im Maschinencode immer schneller sein, weil es weniger Anweisungen und damit weniger CPU-Zyklen erfordert.

Welche ist "besser"?

• Sie sollten "Iteration" verwenden, wenn Sie einfache, sequenzielle 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 eindeutig "eleganter" ist.

Beratung : Verwenden Sie das beste Werkzeug für die jeweilige Aufgabe, aber verstehen Sie die Funktionsweise jedes Werkzeugs, um eine kluge Wahl zu treffen.

Schließlich sollten Sie beachten, dass Sie viele Möglichkeiten haben, die Rekursion zu nutzen. Sie haben Rekursive Datenstrukturen überall, Sie sehen jetzt eines: 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, d.h.: Sie haben ein Root-Verzeichnis, das Dateien und Verzeichnisse enthält, jedes Verzeichnis enthält Dateien und Verzeichnisse, jedes dieser Verzeichnisse enthält Dateien und Verzeichnisse...

Answer 3

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

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

Die richtige Herangehensweise besteht also darin, sie zunächst auf die natürlichste Weise zu schreiben, sie nur dann zu optimieren, wenn die Profilerstellung zeigt, dass sie kritisch ist, und dann die vermeintliche Verbesserung zu messen.

Answer 4

Die meisten Antworten vergessen hier den offensichtlichen Grund, warum Rekursionen oft langsamer sind als iterative Lösungen. Es hängt mit dem Auf- und Abbau von Stackframes zusammen, ist aber nicht genau das. Es ist im Allgemeinen ein großer Unterschied in der Speicherung der Auto-Variablen für jede Rekursion. Bei einem iterativen Algorithmus mit einer Schleife werden die Variablen oft in Registern gehalten, und selbst wenn sie überlaufen, befinden sie sich im Level-1-Cache. In einem rekursiven Algorithmus werden alle Zwischenzustände der Variablen auf dem Stack gespeichert, was bedeutet, dass sie viel häufiger in den Speicher ausgelagert werden. Das bedeutet, dass selbst bei der gleichen Anzahl von Operationen viele Speicherzugriffe in der heißen Schleife erfolgen, und was es noch schlimmer macht, diese Speicheroperationen haben eine schlechte Wiederverwendungsrate, wodurch die Caches weniger effektiv sind.

TL;DR rekursive Algorithmen haben im Allgemeinen ein schlechteres Cache-Verhalten als iterative Algorithmen.

Answer 5

Die meisten der Antworten hier sind falsch . Die richtige Antwort lautet es kommt darauf an . Hier sind zum Beispiel zwei C-Funktionen, die einen Baum durchlaufen. Zuerst die rekursive Funktion:

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 die gleiche Funktion, die mit 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 p Knotenpunkte sind und dass P_FOR_EACH_CHILD macht den Spaziergang. In der iterativen Version benötigen wir einen expliziten Stapel st auf die die Knoten geschoben und dann gepoppt und manipuliert werden.

Die rekursive Funktion läuft viel schneller als die iterative. Der Grund dafür ist, dass bei letzterer für jedes Element eine CALL auf die Funktion st_push benötigt wird und dann eine weitere an st_pop .

Im ersten Fall haben Sie nur die rekursive CALL für jeden Knoten.

Außerdem ist der Zugriff auf Variablen auf dem Aufrufstapel unglaublich schnell. Es bedeutet, dass Sie aus dem Speicher lesen, der sich wahrscheinlich immer im innersten Cache befindet. Ein expliziter Stack hingegen muss durch malloc :ed Speicher aus dem Heap, auf den viel langsamer zugegriffen werden kann.

Bei sorgfältiger Optimierung, wie z. B. dem Inlining st_push y st_pop kann ich mit dem rekursiven Ansatz annähernd Parität 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.

Aber diese Diskussion ist größtenteils überflüssig, denn rekursives Baumlaufen ist falsch . Wenn der Baum groß genug ist, wird der Platz im Aufrufstapel knapp, weshalb ein iterativer Algorithmus verwendet werden muss.