Warum sind Schleifen schneller als Rekursion?

In der Praxis verstehe ich, dass jede Rekursion als Schleife geschrieben werden kann (und umgekehrt (?)), Und wenn wir mit tatsächlichen Computern messen, stellen wir fest, dass Schleifen für dasselbe Problem schneller sind als Rekursion. Aber gibt es eine Theorie, die diesen Unterschied ausmacht, oder ist sie hauptsächlich emprisch?

Der Grund, warum Schleifen schneller sind als Rekursionen, ist einfach.
So sieht eine Schleife in der Montage aus.

mov loopcounter,i
dowork:/do work
dec loopcounter
jmp_if_not_zero dowork

Ein einziger bedingter Sprung und etwas Buchhaltung für den Schleifenzähler.

Die Rekursion (wenn sie vom Compiler nicht optimiert wird oder nicht optimiert werden kann) sieht folgendermaßen aus:

start_subroutine:
pop parameter1
pop parameter2
dowork://dowork
test something
jmp_if_true done
push parameter1
push parameter2
call start_subroutine
done:ret

Es ist viel komplexer und Sie erhalten mindestens 3 Sprünge (1 Test, um zu sehen, ob dies getan wurde, ein Anruf und eine Rückkehr).
Auch bei der Rekursion müssen die Parameter eingerichtet und abgerufen werden.
Keines dieser Dinge wird in einer Schleife benötigt, da alle Parameter bereits eingerichtet sind.

Theoretisch könnten die Parameter auch bei der Rekursion an Ort und Stelle bleiben, aber keine mir bekannten Compiler gehen bei der Optimierung tatsächlich so weit.

Unterschiede zwischen einem Call und einem JMP
Ein Call-Return-Paar ist nicht viel teurer als das JMP. Das Paar benötigt 2 Zyklen und das JMP 1; kaum wahrnehmbar.
In Aufrufkonventionen, die Registerparameter unterstützen, ist der Overhead für Parameter in minimalen, aber auch Stack-Parametern günstig , solange die Puffer der CPU nicht überlaufen .
Es ist der Overhead des Aufrufaufbaus, der durch die verwendete Aufrufkonvention und Parameterbehandlung vorgegeben ist, der die Rekursion verlangsamt.
Dies hängt sehr stark von der Implementierung ab.

Beispiel für eine schlechte Rekursionsbehandlung Wenn beispielsweise ein Parameter übergeben wird, der mit einer Referenzzählung versehen ist (z. B. ein nicht mit einer Konstante verwalteter Typparameter), werden 100 Zyklen hinzugefügt, wodurch die Leistung gegenüber einer Schleife vollständig beeinträchtigt wird.
In Sprachen, die auf Rekursion eingestellt sind, tritt dieses Verhalten nicht auf.

CPU-Optimierung
Der andere Grund, warum die Rekursion langsamer ist, besteht darin, dass sie gegen die Optimierungsmechanismen in CPUs arbeitet.
Renditen können nur dann korrekt vorhergesagt werden, wenn nicht zu viele von ihnen hintereinander liegen. Die CPU verfügt über einen Rückgabepuffer mit einigen wenigen Einträgen. Sobald diese aufgebraucht sind, wird jede zusätzliche Rendite falsch vorhergesagt, was zu enormen Verzögerungen führt.
Auf jeder CPU, die einen Stack Return Buffer verwendet, wird eine aufrufbasierte Rekursion vermieden, die die Puffergröße überschreitet.

Informationen zu einfachen Codebeispielen mit Rekursion
Wenn Sie ein einfaches Beispiel für eine Rekursion wie die Fibonacci-Zahlengenerierung verwenden, treten diese Effekte nicht auf, da jeder Compiler, der über Rekursion Bescheid weiß, diese in eine Schleife umwandelt, genau wie jeder Programmierer, der sein Geld verdient würde.
Wenn Sie diese einfachen Beispiele in einer Umgebung ausführen, die nicht ordnungsgemäß optimiert wird, wächst der Aufrufstapel (unnötigerweise) über die Grenzen hinaus.

Informationen zur Schwanzrekursion
Beachten Sie, dass der Compiler manchmal die Schwanzrekursion optimiert, indem er sie in eine Schleife umwandelt. Es ist am besten, sich nur auf dieses Verhalten in Sprachen zu verlassen, die diesbezüglich eine gute Erfolgsbilanz aufweisen.
Viele Sprachen fügen vor der endgültigen Rückgabe verborgenen Bereinigungscode ein, wodurch die Optimierung der Schwanzrekursion verhindert wird.

Verwechslung zwischen wahrer und Pseudo-Rekursion
Wenn Ihre Programmierumgebung Ihren rekursiven Quellcode in eine Schleife verwandelt, wird möglicherweise keine echte Rekursion ausgeführt.
Für eine echte Rekursion ist ein Vorrat an Breadcrumbs erforderlich, damit die rekursive Routine ihre Schritte nach dem Beenden zurückverfolgen kann.
Es ist die Handhabung dieses Trails, die die Rekursion langsamer macht als die Verwendung einer Schleife. Dieser Effekt wird durch die oben beschriebenen aktuellen CPU-Implementierungen noch verstärkt.

Auswirkung der Programmierumgebung
Wenn Ihre Sprache auf Rekursionsoptimierung eingestellt ist, sollten Sie unbedingt bei jeder Gelegenheit Rekursion verwenden. In den meisten Fällen verwandelt die Sprache Ihre Rekursion in eine Art Schleife.
In den Fällen, in denen dies nicht möglich ist, ist der Programmierer ebenfalls stark belastet. Wenn Ihre Programmiersprache nicht auf Rekursion eingestellt ist, sollte dies vermieden werden, es sei denn, die Domäne ist für Rekursion geeignet.
Leider können viele Sprachen nicht gut mit Rekursion umgehen.

Missbrauch der Rekursion
Es besteht keine Notwendigkeit, die Fibonacci-Sequenz unter Verwendung der Rekursion zu berechnen, tatsächlich handelt es sich um ein pathologisches Beispiel.
Die Rekursion wird am besten in Sprachen verwendet, die sie ausdrücklich unterstützen, oder in Domänen, in denen die Rekursion im Vordergrund steht, z. B. beim Umgang mit Daten, die in einem Baum gespeichert sind.

Ich verstehe, dass jede Rekursion als Schleife geschrieben werden kann

Ja, wenn Sie bereit sind, den Karren vor das Pferd zu stellen.
Alle Instanzen der Rekursion können als Schleife geschrieben werden. Bei einigen dieser Instanzen müssen Sie einen expliziten Stapelspeicher verwenden.
Wenn Sie Ihren eigenen Stack rollen müssen, um rekursiven Code in eine Schleife zu verwandeln, können Sie auch eine einfache Rekursion verwenden.
Es sei denn, Sie haben spezielle Anforderungen wie die Verwendung von Enumeratoren in einer Baumstruktur und verfügen nicht über die richtige Sprachunterstützung.

Diese anderen Antworten sind etwas irreführend. Ich bin damit einverstanden, dass sie Implementierungsdetails angeben, die diese Ungleichheit erklären können, aber sie übertreiben den Fall. Wie richtig von jmite vorgeschlagen, sie sind umsetzungsorientiert in Richtung gebrochen Implementierungen von Funktionsaufrufen / Rekursion. Viele Sprachen implementieren Schleifen über Rekursion, so dass Schleifen in diesen Sprachen eindeutig nicht schneller sind. Die Rekursion ist theoretisch in keiner Weise weniger effizient als das Schleifen (wenn beide anwendbar sind). Lassen Sie mich den Auszug aus Guy Steeles 1977 erschienenen Aufsatz zitieren, in dem der Mythos "Expensive Procedure Call" entlarvt wird

Folklore besagt, dass GOTO-Anweisungen "billig" sind, während Prozeduraufrufe "teuer" sind. Dieser Mythos ist größtenteils auf schlecht gestaltete Sprachimplementierungen zurückzuführen. Das historische Wachstum dieses Mythos wird berücksichtigt. Es werden sowohl theoretische Ideen als auch eine bestehende Implementierung diskutiert, die diesen Mythos entlarven. Es zeigt sich, dass die uneingeschränkte Verwendung von Prozeduraufrufen eine große stilistische Freiheit erlaubt. Insbesondere kann jedes Flussdiagramm als "strukturiertes" Programm geschrieben werden, ohne zusätzliche Variablen einzuführen. Die Schwierigkeit mit der GOTO-Anweisung und dem Prozeduraufruf wird als Konflikt zwischen abstrakten Programmierkonzepten und konkreten Sprachkonstrukten charakterisiert.

Der "Konflikt zwischen abstrakten Programmierkonzepten und konkreten Sprachkonstrukten" zeigt sich daran, dass die meisten theoretischen Modelle, zum Beispiel der untypisierte Lambda-Kalkül , keinen Stapel haben . Natürlich ist dieser Konflikt nicht notwendig, wie das obige Papier zeigt und wie auch Sprachen zeigen, die keinen anderen Iterationsmechanismus als die Rekursion haben, wie Haskell.

Lass es mich demonstrieren. Der Einfachheit halber werde ich einen "angewendeten" Lambda-Kalkül mit Zahlen und und Booleschen Werten verwenden und davon ausgehen, dass wir einen Festkomma-Kombinator haben fix, der befriedigt fix f x = f (fix f) x. All dies kann auf die untypisierte Lambda-Rechnung reduziert werden, ohne mein Argument zu ändern. Der archetypische Weg zum Verständnis der Bewertung des Lambda-Kalküls ist das Umschreiben von Begriffen mit der zentralen Umschreiberegel der Beta-Reduktion, nämlich wobei "alles frei ersetzen" bedeutet Vorkommen von in mit "und$(\lambda x.M)N \leadsto M[N/x]$x M N $[N/x]$$x$$M$$N$$\leadsto$bedeutet "schreibt um". Dies ist nur die Formalisierung des Ersetzens der Argumente eines Funktionsaufrufs in den Funktionskörper.

Nun zum Beispiel. Definiere factals

fact = fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 1

Hier ist die Bewertung von fact 3, wo für die Kompaktheit, ich gals Synonym für fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)), dh verwenden werde fact = g 1. Dies hat keinen Einfluss auf mein Argument.

fact 3 
~> g 1 3
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 1 3 
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 1 3
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 1 3
~> (λn.if n == 0 then 1 else g (1*n) (n-1)) 3
~> if 3 == 0 then 1 else g (1*3) (3-1)
~> g (1*3) (3-1)
~> g 3 2
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 3 2
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 3 2
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 3 2
~> (λn.if n == 0 then 3 else g (3*n) (n-1)) 2
~> if 2 == 0 then 3 else g (3*2) (2-1)
~> g (3*2) (2-1)
~> g 6 1
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 6 1
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 6 1
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 6 1
~> (λn.if n == 0 then 6 else g (6*n) (n-1)) 1
~> if 1 == 0 then 6 else g (6*1) (1-1)
~> g (6*1) (1-1)
~> g 6 0
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 6 0
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 6 0
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 6 0
~> (λn.if n == 0 then 6 else g (6*n) (n-1)) 0
~> if 0 == 0 then 6 else g (6*0) (0-1)
~> 6

Sie können an der Form erkennen, ohne die Details zu betrachten, dass es kein Wachstum gibt und jede Iteration dieselbe Menge an Platz benötigt. (Technisch gesehen wächst das numerische Ergebnis, was für eine whileSchleife unvermeidlich und genauso wahr ist.) Ich fordere Sie heraus, hier auf den grenzenlos wachsenden "Stapel" hinzuweisen.

Es scheint, dass die archetypische Semantik des Lambda-Kalküls bereits das tut, was gemeinhin als "Tail-Call-Optimierung" bezeichnet wird. Natürlich findet hier keine "Optimierung" statt. Es gibt hier keine speziellen Regeln für "Tail" -Anrufe im Gegensatz zu "normalen" Anrufen. Aus diesem Grund ist es schwierig, eine "abstrakte" Charakterisierung dessen zu geben, was die "Optimierung" des Endaufrufs bewirkt, da in vielen abstrakten Charakterisierungen der Funktionsaufrufsemantik nichts für die "Optimierung" des Endaufrufs zu tun ist!

Dass die analoge Definition von factin vielen Sprachen "Stack Overflows" ein Versagen dieser Sprachen ist, Funktionsaufrufsemantik korrekt zu implementieren. (Einige Sprachen haben eine Entschuldigung.) Die Situation ist ungefähr analog zu einer Sprachimplementierung, die Arrays mit verknüpften Listen implementiert. Das Indizieren in solche "Arrays" wäre dann eine O (n) -Operation, die die Erwartungen von Arrays nicht erfüllt. Wenn ich eine separate Implementierung der Sprache vornehmen würde, die echte Arrays anstelle von verknüpften Listen verwendet, würden Sie nicht sagen, dass ich "Array-Zugriffsoptimierung" implementiert habe, sondern, dass ich eine fehlerhafte Implementierung von Arrays behoben habe.

Also, auf die Antwort von Veedrac antworten. Stapel sind für eine Rekursion nicht "grundlegend" . Soweit im Verlauf der Auswertung ein "stapelartiges" Verhalten auftritt, kann dies nur in Fällen vorkommen, in denen Schleifen (ohne Hilfsdatenstruktur) überhaupt nicht anwendbar wären! Anders ausgedrückt, ich kann Schleifen mit Rekursion mit genau den gleichen Leistungsmerkmalen implementieren. Tatsächlich enthalten sowohl Scheme als auch SML Schleifenkonstrukte, aber beide definieren diese in Bezug auf Rekursion (und werden zumindest in Scheme dohäufig als Makro implementiert , das sich zu rekursiven Aufrufen erweitert.) In ähnlicher Weise sagt für Johans Antwort nichts a Der Compiler muss die von Johan beschriebene Assembly für die Rekursion ausgeben. Tatsächlich,genau die gleiche Assembly, ob Sie Schleifen oder Rekursion verwenden. Das einzige Mal, dass der Compiler (etwas) verpflichtet wäre , Assemblys wie das, was Johan beschreibt, zu senden, ist, wenn Sie etwas tun, das durch eine Schleife sowieso nicht ausgedrückt werden kann. Wie in Steeles Aufsatz dargelegt und anhand der tatsächlichen Praxis von Sprachen wie Haskell, Scheme und SML demonstriert, ist es nicht "außerordentlich selten", dass Tail Calls "optimiert" werden können, sondern immer"optimiert" werden. Ob eine bestimmte Verwendung der Rekursion in einem konstanten Raum ausgeführt wird, hängt davon ab, wie sie geschrieben wurde. Die Einschränkungen, die Sie anwenden müssen, um dies zu ermöglichen, sind jedoch die Einschränkungen, die Sie benötigen, um Ihr Problem in die Form einer Schleife zu bringen. (Tatsächlich sind sie weniger streng. Es gibt Probleme wie das Codieren von Zustandsautomaten, die über Tails-Aufrufe sauberer und effizienter gehandhabt werden als Schleifen, die Hilfsvariablen erfordern würden.) Auch hier ist die einzige Zeit, in der die Rekursion mehr Arbeit erfordert, die Durchführung wenn dein Code sowieso keine Schleife ist.

Ich vermute, Johan bezieht sich auf C-Compiler, die willkürliche Einschränkungen haben, wann sie die Tail-Call- "Optimierung" durchführen. Johan spricht vermutlich auch von Sprachen wie C ++ und Rust, wenn es um "Sprachen mit verwalteten Typen" geht. Das RAII- Idiom aus C ++ und auch in Rust macht Dinge, die oberflächlich wie Tail Calls aussehen, nicht wie Tail Calls (weil die "Destruktoren" noch aufgerufen werden müssen). Es hat Vorschläge gegeben, eine andere Syntax zu verwenden, um sich für eine etwas andere Semantik zu entscheiden, die eine Schwanzrekursion ermöglichen würde (d. H. Aufrufdestruktoren zuvor)der letzte Tail Call und offensichtlich nicht auf "zerstörte" Objekte zugreifen zu dürfen). (Bei der Garbage Collection gibt es kein solches Problem, und alle Sprachen von Haskell, SML und Scheme sind Garbage Collected-Sprachen.) In einer ganz anderen Art und Weise machen einige Sprachen, wie z. B. Smalltalk, den "Stapel" als erstklassiges Objekt in diesen Sprachen verfügbar In einigen Fällen ist der "Stapel" kein Implementierungsdetail mehr, was jedoch separate Aufruftypen mit unterschiedlicher Semantik nicht ausschließt. (Java sagt, dass dies aufgrund der Art und Weise, wie einige Sicherheitsaspekte behandelt werden, nicht möglich ist , aber dies ist tatsächlich falsch .)

In der Praxis kommt die Prävalenz fehlerhafter Implementierungen von Funktionsaufrufen von drei Hauptfaktoren. Erstens erben viele Sprachen die fehlerhafte Implementierung von ihrer Implementierungssprache (normalerweise C). Zweitens ist deterministisches Ressourcenmanagement nett und kompliziert das Thema, obwohl nur eine Handvoll Sprachen dies bieten. Drittens, und meiner Erfahrung nach interessieren sich die meisten Menschen dafür, dass sie Stack-Traces benötigen, wenn Fehler zu Debug-Zwecken auftreten. Nur der zweite Grund kann möglicherweise theoretisch motiviert sein.

Grundsätzlich besteht der Unterschied darin, dass die Rekursion einen Stapel enthält, eine Hilfsdatenstruktur, die Sie wahrscheinlich nicht möchten, während dies bei Schleifen nicht automatisch der Fall ist. Nur in seltenen Fällen kann ein typischer Compiler feststellen, dass Sie den Stack nicht wirklich benötigen.

Wenn Sie stattdessen Schleifen vergleichen, die manuell auf einem zugewiesenen Stapel ausgeführt werden (z. B. durch einen Zeiger auf den Heapspeicher), werden Sie sie normalerweise nicht schneller oder sogar langsamer vorfinden als bei Verwendung des Hardware-Stapels.