Rekursion oder while-Schleifen

123

Ich habe über einige Praktiken für Entwicklungsinterviews gelesen, insbesondere über die technischen Fragen und Tests, die bei den Interviews gestellt wurden, und bin einige Male über Sprüche des Genres gestolpert. "Ok, Sie haben das Problem mit einer while-Schleife gelöst, jetzt können Sie es tun Rekursion "oder" Jeder kann dies mit einer 100-Zeilen-while-Schleife lösen, aber können sie dies mit einer 5-Zeilen-Rekursionsfunktion tun? " usw.

Meine Frage ist, ist Rekursion im Allgemeinen besser als wenn / während / für Konstrukte?

Ich habe ehrlich gesagt immer gedacht, dass Rekursion nicht zu bevorzugen ist, da sie auf den Stapelspeicher beschränkt ist, der viel kleiner als der Heap ist. Auch das Ausführen einer großen Anzahl von Funktions- / Methodenaufrufen ist vom Standpunkt der Leistung aus nicht optimal, aber ich kann falsch liegen...

Shivan Drache
quelle
73
Zum Thema Rekursion, dies sieht ganz interessant.
dan_waterworth
4
@ dan_waterworth auch das würde helfen: google.fr/… aber ich scheine es immer falsch zu buchstabieren: P
Shivan Dragon
@ShivanDragon fand ich so ^ _ ^ Sehr passend, dass ich es gestern gepostet habe :-)
Neal
2
In den eingebetteten Umgebungen, in denen ich rekursiv gearbeitet habe, wird es bestenfalls verpönt und Sie werden im schlimmsten Fall öffentlich ausgepeitscht. Der begrenzte Stapelspeicherplatz macht es illegal.
Fred Thomsen

Antworten:

192

Rekursion ist an sich nicht besser oder schlechter als Schleifen - jede hat Vor- und Nachteile, und diese hängen sogar von der Programmiersprache (und der Implementierung) ab.

Technisch gesehen passen iterative Schleifen besser zu typischen Computersystemen auf Hardwareebene: Auf Maschinencodeebene ist eine Schleife nur ein Test und ein bedingter Sprung, während die Rekursion (naiv implementiert) das Verschieben eines Stapelrahmens, das Springen, Zurückkehren und Zurückspringen umfasst vom Stapel. OTOH, viele Fälle von Rekursion (insbesondere solche, die trivial zu iterativen Schleifen äquivalent sind) können so geschrieben werden, dass der Stack-Push / Pop vermieden werden kann; Dies ist möglich, wenn der rekursive Funktionsaufruf das letzte Ereignis im Funktionskörper ist, bevor er zurückgegeben wird. Dies wird im Allgemeinen als Tail-Call-Optimierung (oder Tail-Recursion-Optimierung ) bezeichnet. Eine ordnungsgemäß tail-call-optimierte rekursive Funktion entspricht meist einer iterativen Schleife auf Maschinencodeebene.

Eine weitere Überlegung ist, dass iterative Schleifen destruktive Zustandsaktualisierungen erfordern, die sie mit der reinen (nebenwirkungsfreien) Sprachsemantik inkompatibel machen. Dies ist der Grund, warum reine Sprachen wie Haskell überhaupt keine Schleifenkonstrukte haben und viele andere funktionale Programmiersprachen sie entweder nicht vollständig oder so weit wie möglich meiden.

Der Grund, warum diese Fragen in Interviews so häufig vorkommen, ist, dass Sie zur Beantwortung vieler wichtiger Programmierkonzepte - Variablen, Funktionsaufrufe, Gültigkeitsbereiche und natürlich Schleifen und Rekursionen - genauestens verstehen müssen die mentale Flexibilität auf den Tisch zu bringen, die es Ihnen ermöglicht, ein Problem aus zwei radikal unterschiedlichen Blickwinkeln anzusprechen und zwischen verschiedenen Erscheinungsformen desselben Konzepts zu wechseln.

Erfahrungs- und Forschungsergebnisse legen nahe, dass es eine Grenze zwischen Menschen gibt, die Variablen, Zeiger und Rekursionen verstehen können, und solchen, die dies nicht tun. Fast alles andere in der Programmierung, einschließlich Frameworks, APIs, Programmiersprachen und deren Randbedingungen, kann durch Studium und Erfahrung erlangt werden. Wenn Sie jedoch keine Intuition für diese drei Kernkonzepte entwickeln können, sind Sie nicht in der Lage, Programmierer zu sein. Das Übersetzen einer einfachen iterativen Schleife in eine rekursive Version ist die schnellste Methode zum Herausfiltern von Nicht-Programmierern. Selbst ein unerfahrener Programmierer kann dies in der Regel in 15 Minuten tun, und es ist ein sehr sprachunabhängiges Problem, das der Kandidat auswählen kann eine Sprache ihrer Wahl, anstatt über Eigenheiten zu stolpern.

Wenn Sie in einem Interview eine Frage wie diese erhalten, ist dies ein gutes Zeichen: Der potenzielle Arbeitgeber sucht nach Personen, die programmieren können, und nicht nach Personen, die sich das Handbuch eines Programmierwerkzeugs auswendig gelernt haben.

tdammers
quelle
3
Ihre Antwort gefällt mir am besten, weil sie die wichtigsten Aspekte berührt, die eine Antwort auf diese Frage haben könnte, die wichtigsten technischen Teile erklärt und auch eine gute vergrößerte Ansicht darüber gibt, wie dieses Problem in die Programmiersphäre passt.
Shivan Dragon
1
Mir ist auch ein Muster in einer Synchronisationsprogrammierung aufgefallen, bei dem Schleifen zugunsten rekursiver Aufrufe eines Iterators vermieden werden, der eine .next () - Methode enthält. Ich nehme an, es verhindert, dass lang laufender Code zu CPU-gierig wird.
Evan Plaice
1
Bei der iterativen Version werden auch Werte verschoben und abgelegt. Sie müssen nur den Code manuell schreiben, um dies zu tun. In der rekursiven Version wird der Status in einem iterativen Algorithmus auf den Stapel verschoben, den Sie normalerweise manuell simulieren müssen, indem Sie den Status in eine bestimmte Struktur verschieben. Nur die einfachsten Algorithmen benötigen diesen Status nicht. In diesen Fällen kann der Compiler normalerweise die Schwanzrekursion erkennen und eine iterative Lösung erstellen.
Martin York
1
@tdammers Könnten Sie mir sagen, wo ich die Studie lesen kann, die Sie erwähnt haben? "Erfahrungen und Untersuchungen legen nahe, dass es eine Grenze zwischen Menschen gibt ..." Dies scheint für mich sehr interessant zu sein.
Yoo Matsuo
2
Sie haben vergessen zu erwähnen, dass iterativer Code in der Regel eine bessere Leistung erzielt, wenn Sie mit einem einzelnen Ausführungsthread arbeiten. Rekursive Algorithmen können jedoch auch in mehreren Threads ausgeführt werden.
GordonM
37

Es hängt davon ab, ob.

  • Einige Probleme sind sehr anfällig für rekursive Lösungen, z. B. Quicksort
  • Einige Sprachen unterstützen keine Rekursion, zB frühe FORTRANs
  • Einige Sprachen nehmen eine Rekursion als primäres Mittel zum Schleifen an, z. B. Haskell

Es ist auch erwähnenswert, dass durch die Unterstützung der Schwanzrekursion die rekursiven und iterativen Schleifen des Schwanzes gleichgesetzt werden. Das heißt, die Rekursion muss nicht immer den Stapel verschwenden.

Ein rekursiver Algorithmus kann auch immer iterativ implementiert werden, indem ein expliziter Stapel verwendet wird .

Schließlich würde ich bemerken, dass eine Lösung mit fünf Zeilen wahrscheinlich immer besser ist als eine Lösung mit 100 Zeilen (vorausgesetzt, sie sind tatsächlich gleichwertig).

jk.
quelle
5
Schöne Antwort (+1). "Eine 5-Zeilen-Lösung ist wahrscheinlich immer besser als eine 100-Zeilen-Lösung": Ich denke, Prägnanz ist nicht der einzige Vorteil der Rekursion. Durch die Verwendung eines rekursiven Aufrufs werden Sie gezwungen, die funktionalen Abhängigkeiten zwischen Werten in verschiedenen Iterationen explizit anzugeben.
Giorgio
4
Kürzere Lösungen sind in der Regel besser, aber es gibt eine zu knappe Lösung.
dan_waterworth
5
@dan_waterworth im Vergleich zu „100 line“ es ist ziemlich schwierig zu sein , allzu kurz und bündig
gnat
4
@ Giorgio, Sie können Programme verkleinern, indem Sie unnötigen Code entfernen oder explizite Dinge implizieren. Solange Sie an ersterem festhalten, verbessern Sie die Qualität.
dan_waterworth
1
@jk, ich denke, das ist eine andere Form, explizite Informationen implizit zu machen. Die Informationen darüber, wofür eine Variable verwendet wird, werden aus ihrem Namen entfernt, wo sie explizit ist, und in ihre implizite Verwendung übertragen.
Dan_waterworth
17

Es gibt keine allgemein anerkannte Definition von "besser", wenn es um Programmierung geht, aber ich nehme es als "leichter zu warten / zu lesen".

Rekursion hat mehr Ausdruckskraft als iterative Schleifenkonstrukte: Ich sage dies, weil eine while-Schleife einer rekursiven Tail-Funktion entspricht und rekursive Funktionen nicht rekursiv sein müssen. Leistungsfähige Konstrukte sind in der Regel eine schlechte Sache, weil sie es Ihnen ermöglichen, schwer lesbare Dinge zu tun. Rekursion gibt Ihnen jedoch die Möglichkeit, Schleifen ohne Verwendung von Mutability zu schreiben, und meiner Meinung nach ist Mutability viel leistungsfähiger als Rekursion.

Von niedriger Ausdrucksstärke zu hoher Ausdrucksstärke stapeln sich Schleifen-Konstrukte wie folgt:

  • Rekursive Funktionen, die unveränderliche Daten verwenden,
  • Rekursive Funktionen, die unveränderliche Daten verwenden,
  • While-Schleifen, die veränderbare Daten verwenden,
  • Schwanzrekursive Funktionen, die veränderbare Daten verwenden,
  • Rekursive Funktionen, die veränderbare Daten verwenden,

Im Idealfall würden Sie die am wenigsten aussagekräftigen Konstrukte verwenden, die Sie können. Wenn Ihre Sprache die Tail-Call-Optimierung nicht unterstützt, kann dies natürlich auch Ihre Wahl des Loop-Konstrukts beeinflussen.

dan_waterworth
quelle
1
msgstr "eine while - Schleife entspricht einer rekursiven Schwanzfunktion und rekursive Funktionen müssen nicht rekursiv sein": +1. Sie können die Rekursion mit einer while-Schleife + einem Stapel simulieren.
Giorgio
1
Ich bin mir nicht sicher, ob ich 100% einverstanden bin, aber es ist sicherlich eine interessante Perspektive, also +1 dafür.
Konrad Rudolph
+1 für eine gute Antwort und auch um zu erwähnen, dass einige Sprachen (oder Compiler) keine Tail-Call-Optimierungen durchführen.
Shivan Dragon
@ Giorgio, "Sie können die Rekursion mithilfe einer while-Schleife + eines Stapels simulieren". Deshalb habe ich Ausdruckskraft gesagt. Sie sind rechnerisch gleichermaßen leistungsfähig.
Dan_waterworth
@dan_waterworth: Genau, und wie Sie in Ihrer Antwort gesagt haben, ist die Rekursion allein aussagekräftiger als eine while-Schleife, da Sie einer while-Schleife einen Stapel hinzufügen müssen, um die Rekursion zu simulieren.
Giorgio
7

Rekursion ist oft weniger offensichtlich. Weniger offensichtlich ist schwerer zu pflegen.

Wenn Sie for(i=0;i<ITER_LIMIT;i++){somefunction(i);}im Hauptablauf schreiben , stellen Sie klar, dass Sie eine Schleife schreiben. Wenn Sie schreiben, machen somefunction(ITER_LIMIT);Sie nicht wirklich klar, was passieren wird. Nur Inhalte sehen: Dieser somefunction(int x)Aufruf zeigt an somefunction(x-1), dass es sich tatsächlich um eine Schleife handelt, die Iterationen verwendet. Außerdem können Sie eine Escape-Bedingung nicht einfach break;irgendwo in der Mitte der Iterationen platzieren. Sie müssen entweder eine Bedingung hinzufügen, die auf dem gesamten Weg zurückgegeben wird, oder eine Ausnahme auslösen. (Und Ausnahmen machen nochmal komplizierter ...)

Im Wesentlichen, wenn es eine offensichtliche Wahl zwischen Iteration und Rekursion ist, machen Sie die intuitive Sache. Wenn die Iteration die Aufgabe leicht erledigt, lohnt sich das Speichern von 2 Zeilen auf lange Sicht nur selten.

Wenn Sie 98 Zeilen sparen, ist das natürlich eine ganz andere Sache.

Es gibt Situationen, für die Rekursion einfach perfekt passt und die nicht wirklich ungewöhnlich sind. Durchquerung von Baumstrukturen, mehrfach verknüpften Netzwerken, Strukturen, die ihren eigenen Typ enthalten können, mehrdimensionale gezackte Arrays, im Wesentlichen alles, was weder ein einfacher Vektor noch ein Array fester Dimensionen ist. Wenn Sie einen bekannten, geraden Pfad durchlaufen, iterieren Sie. Wenn Sie in Unbekanntes eintauchen, greifen Sie zu.

Grundsätzlich sollten Sie somefunction(x-1)Iterationen vergessen , wenn Sie mehr als einmal pro Ebene von sich aus aufrufen möchten.

... Das iterative Schreiben von Funktionen für Aufgaben, die am besten durch Rekursion erledigt werden, ist möglich, aber nicht angenehm. Wo immer Sie möchten int, brauchen Sie etwas wie stack<int>. Ich habe es einmal gemacht, mehr als Übung als zu praktischen Zwecken. Ich kann Ihnen versichern, dass Sie, wenn Sie erst einmal vor einer solchen Aufgabe stehen, keine Zweifel mehr haben werden, wie Sie es ausdrückten.

SF.
quelle
10
Was offensichtlich und was weniger offensichtlich ist, hängt teilweise davon ab, an was Sie gewöhnt sind. Iteration wird in Programmiersprachen häufiger verwendet, da sie der Arbeitsweise der CPU näher kommt (dh weniger Arbeitsspeicher benötigt und schneller ausgeführt wird). Aber wenn Sie es gewohnt sind, induktiv zu denken, kann Rekursion genauso intuitiv sein.
Giorgio
5
"Wenn sie ein Loop-Schlüsselwort sehen, wissen sie, dass es eine Schleife ist. Es gibt jedoch kein Recurse-Schlüsselwort. Sie können es nur erkennen, indem sie f (x-1) in f (x) sehen.": Wenn Sie eine rekursive Funktion aufrufen, tun Sie dies will nicht wissen, dass es rekursiv ist. Wenn Sie eine Funktion aufrufen, die eine Schleife enthält, möchten Sie nicht wissen, dass sie eine Schleife enthält.
Giorgio
3
@SF: Ja, aber das können Sie nur sehen, wenn Sie sich den Funktionsumfang ansehen. Im Falle einer Schleife sehen Sie die Schleife, im Falle einer Rekursion sehen Sie, dass die Funktion sich selbst aufruft.
Giorgio
5
@SF: Scheint mir ein bisschen nach Zirkelschluss zu sein: "Wenn es in meiner Intuition eine Schleife ist, dann ist es eine Schleife." mapkann als rekursive Funktion definiert werden (siehe z. B. haskell.org/tutorial/functions.html ), auch wenn intuitiv klar ist, dass sie eine Liste durchläuft und auf jedes Mitglied der Liste eine Funktion anwendet.
Giorgio
5
@SF mapist kein Schlüsselwort, es ist eine reguläre Funktion, aber das ist ein wenig irrelevant. Wenn funktionale Programmierer eine Rekursion verwenden, liegt dies normalerweise nicht daran, dass sie eine Abfolge von Aktionen ausführen möchten, sondern daran, dass das zu lösende Problem als Funktion und als Liste von Argumenten ausgedrückt werden kann. Das Problem kann dann auf eine andere Funktion und eine andere Liste von Argumenten reduziert werden. Schließlich haben Sie ein Problem, das trivial gelöst werden kann.
Dan_waterworth
6

Wie üblich ist dies im Allgemeinen nicht zu beantworten, da es zusätzliche Faktoren gibt, die in der Praxis zwischen den Fällen weitestgehend ungleich und innerhalb eines Anwendungsfalls ungleich sind. Hier sind einige der Belastungen.

  • Kurzer, eleganter Code ist im Allgemeinen langem, komplexem Code überlegen.
  • Der letzte Punkt ist jedoch etwas ungültig, wenn Ihre Entwicklerbasis nicht mit Rekursion vertraut ist und nicht bereit / nicht in der Lage ist zu lernen. Es kann sogar eher ein leichtes Negativ als ein Positiv werden.
  • Die Rekursion kann für die Effizienz schlecht sein, wenn Sie in der Praxis stark verschachtelte Aufrufe benötigen und die Schwanzrekursion nicht verwenden können (oder wenn Ihre Umgebung die Schwanzrekursion nicht optimieren kann).
  • Die Rekursion ist in vielen Fällen auch dann schlecht, wenn Sie Zwischenergebnisse nicht ordnungsgemäß zwischenspeichern können. Das übliche Beispiel für die Verwendung der Baumrekursion zur Berechnung von Fibonacci-Zahlen ist beispielsweise fürchterlich schlecht, wenn Sie nicht zwischenspeichern. Wenn Sie zwischenspeichern, ist es einfach, schnell, elegant und insgesamt wunderbar.
  • Die Rekursion ist in einigen Fällen nicht anwendbar, genauso gut wie die Iteration in anderen und in anderen Fällen absolut notwendig. Das Durchlaufen langer Ketten von Geschäftsregeln wird normalerweise überhaupt nicht durch Rekursion unterstützt. Das Iterieren durch Datenströme kann mit Rekursion sinnvoll durchgeführt werden. Das Iterieren über mehrdimensionale dynamische Datenstrukturen (z. B. Labyrinthe, Objektbäume ...) ist ohne Rekursion, explizit oder implizit, so gut wie unmöglich. Beachten Sie, dass in diesen Fällen die explizite Rekursion viel besser ist als die implizite - nichts ist schmerzhafter als das Lesen von Code, bei dem jemand seinen eigenen unvollständigen, fehlerhaften Ad-hoc-Stapel innerhalb der Sprache implementiert, um das unheimliche R-Wort zu vermeiden.
Kilian Foth
quelle
Was meinen Sie mit Caching in Bezug auf Rekursion?
Giorgio
@ Giorgio vermutlich Memoization
jk.
Feh. Wenn Ihre Umgebung die Tail Calls nicht optimiert, sollten Sie eine bessere Umgebung finden, und wenn Ihre Entwickler mit Rekursion nicht vertraut sind, sollten Sie bessere Entwickler finden. Haben Sie einige Standards, Leute!
CA McCann
1

Bei der Rekursion wird der Funktionsaufruf wiederholt, bei der Schleife wird der Sprung zum Speicherplatz wiederholt.

Sollte auch über Stapelüberlauf erwähnt werden - http://en.wikipedia.org/wiki/Stack_overflow

Okobaka
quelle
1
Rekursion bedeutet eine Funktion, deren Definition darin besteht, sich selbst aufzurufen.
Hardmath
1
Ihre einfache Definition ist zwar nicht 100% genau, aber Sie sind der einzige, der einen Stapelüberlauf erwähnt hat.
Qix
1

Es kommt wirklich auf die Bequemlichkeit oder die Anforderung an:

Wenn Sie die Programmiersprache Python verwenden , wird die Rekursion unterstützt. Standardmäßig ist die Rekursionstiefe jedoch auf 1000 begrenzt. Wenn es den Grenzwert überschreitet, erhalten wir einen Fehler oder eine Ausnahme. Diese Grenze kann geändert werden, aber wenn wir dies tun, kann es zu abnormalen Situationen in der Sprache kommen.

Zu diesem Zeitpunkt (Anzahl der Aufrufe mehr als Rekursionstiefe) müssen wir Schleifenkonstrukte bevorzugen. Ich meine, wenn die Stapelgröße nicht ausreicht, müssen wir die Schleifenkonstrukte bevorzugen.

usernaveen
quelle
3
Hier ist ein Blog von Guido van Rossum, in dem er erklärt, warum er keine Optimierung der Schwanzrekursion in Python wünscht (was die Annahme unterstützt, dass verschiedene Sprachen unterschiedliche taktische Ansätze verfolgen).
Hardmath
-1

Verwenden Sie das Strategieentwurfsmuster.

  • Rekursion ist sauber
  • Loops sind (wohl) effizient

Wählen Sie je nach Belastung (und / oder anderen Bedingungen) eine aus.

Pravin Sonawane
quelle
5
Warte was? Wie passt das Strategiemuster hierher? Und der zweite Satz klingt wie eine leere Phrase.
Konrad Rudolph
@KonradRudolph Ich würde für die Rekursion gehen. Bei sehr großen Datenmengen würde ich auf Schleifen umstellen. Das ist es was ich meinte. Ich entschuldige mich, wenn es nicht klar war.
Pravin Sonawane
3
Ah. Nun, ich bin mir immer noch nicht sicher, ob dies als "Strategie-Design-Muster" bezeichnet werden kann, das eine sehr feste Bedeutung hat und das Sie metaphorisch verwenden. Aber jetzt sehe ich wenigstens, wohin du gehst.
Konrad Rudolph
@KonradRudolph hat eine wichtige Lektion gelernt. Erklären Sie
ausführlich
2
@Pravin Sonawane: Wenn Sie die Schwanzrekursionsoptimierung verwenden können, können Sie die Rekursion auch für große Datenmengen verwenden.
Giorgio