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

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.

Answer 2

Überlegen Sie, was unbedingt für jede Iteration und Rekursion getan werden muss.

• Iteration: ein Sprung zum Schleifenanfang
• Rekursion: ein Sprung zum Anfang der aufgerufenen Funktion

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

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

Answer 3

Im Allgemeinen ist eine Rekursion nicht schneller als eine Schleife in jeder realistischen Anwendung, die in beiden Formen praktikable Implementierungen hat. Sicher, man kann Schleifen programmieren, die ewig dauern, aber es gibt bessere Möglichkeiten, dieselbe Schleife zu implementieren, die jede Implementierung desselben Problems durch Rekursion übertreffen.

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

Beachten Sie jedoch, dass ich gesagt habe, dass es "praktikable Umsetzungen in beiden Formen" gibt. Für Dinge wie viele Sortieralgorithmen gibt es in der Regel keine praktikable Möglichkeit, sie zu implementieren, die nicht effektiv eine eigene Version eines Stapels einrichtet, da immer wieder untergeordnete "Aufgaben" erzeugt werden, die von Natur aus Teil des Prozesses sind. Daher kann eine Rekursion genauso schnell sein wie der Versuch, den Algorithmus in einer Schleife zu implementieren.

Edit: Diese Antwort geht von nicht-funktionalen Sprachen aus, in denen die meisten grundlegenden Datentypen veränderbar sind. Sie gilt nicht für funktionale Sprachen.

Answer 4

In einem realistischen System wird die Erstellung eines Stack Frames immer teurer sein als ein INC und ein JMP. Aus diesem Grund wandeln wirklich gute Compiler die Tail-Rekursion automatisch in einen Aufruf desselben Frames um, d.h. ohne den Overhead, so dass Sie die besser lesbare Quelltextversion und die effizientere kompilierte Version erhalten. A wirklich, wirklich Ein guter Compiler sollte sogar in der Lage sein, eine normale Rekursion in eine Tail-Rekursion umzuwandeln, sofern dies möglich ist.

Answer 5

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

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

Aus der Sicht eines Programmierers kommt es mehr auf die Lesbarkeit und Wartbarkeit an als auf die Optimierung. Auch hier gilt: "Verfrühte Optimierung ist die Wurzel allen Übels".