Eines der Themen, die anscheinend regelmäßig in Mailinglisten und Online-Diskussionen auftauchen, sind die Vorzüge (oder das Fehlen davon) eines Informatik-Abschlusses. Ein Argument, das für die negative Partei immer wieder auftaucht, ist, dass sie seit einigen Jahren codiert und nie eine Rekursion verwendet hat.
Die Frage ist also:
- Was ist Rekursion?
- Wann würde ich Rekursion verwenden?
- Warum verwenden die Leute keine Rekursion?
recursion
computer-science
Mike Minutillo
quelle
quelle
Antworten:
In diesem Thread gibt es eine Reihe guter Erklärungen für die Rekursion. In dieser Antwort geht es darum, warum Sie sie in den meisten Sprachen nicht verwenden sollten. * In den meisten wichtigen imperativen Sprachimplementierungen (dh jeder wichtigen Implementierung von C, C ++, Basic, Python) , Ruby-, Java- und C # -Iteration ist der Rekursion weit vorzuziehen.
Gehen Sie die Schritte aus, mit denen die oben genannten Sprachen eine Funktion aufrufen, um zu sehen, warum:
Das Ausführen all dieser Schritte erfordert Zeit, normalerweise etwas mehr als das Durchlaufen einer Schleife. Das eigentliche Problem liegt jedoch in Schritt 1. Wenn viele Programme gestartet werden, weisen sie ihrem Stapel einen einzelnen Speicherblock zu, und wenn ihnen der Speicher ausgeht (häufig, aber nicht immer aufgrund von Rekursion), stürzt das Programm aufgrund eines Stapelüberlaufs ab .
In diesen Sprachen ist die Rekursion also langsamer und macht Sie anfällig für Abstürze. Es gibt jedoch noch einige Argumente für die Verwendung. Im Allgemeinen ist rekursiv geschriebener Code kürzer und etwas eleganter, sobald Sie wissen, wie man ihn liest.
Es gibt eine Technik, die Sprachimplementierer verwenden können, die sogenannte Tail-Call-Optimierung, mit der einige Klassen von Stapelüberläufen beseitigt werden können. Kurz gesagt: Wenn der Rückgabeausdruck einer Funktion einfach das Ergebnis eines Funktionsaufrufs ist, müssen Sie dem Stapel keine neue Ebene hinzufügen, sondern können die aktuelle Ebene für die aufgerufene Funktion wiederverwenden. Bedauerlicherweise ist in wenigen imperativen Sprachimplementierungen eine Tail-Call-Optimierung integriert.
* Ich liebe Rekursion. Meine statische Lieblingssprache verwendet überhaupt keine Schleifen, Rekursion ist die einzige Möglichkeit, etwas wiederholt zu tun. Ich denke einfach nicht, dass Rekursion in Sprachen, die nicht darauf abgestimmt sind, im Allgemeinen eine gute Idee ist.
** Übrigens, Mario, der typische Name für Ihre ArrangeString-Funktion ist "join", und ich wäre überrascht, wenn Ihre Sprache Ihrer Wahl noch keine Implementierung hat.
quelle
Einfaches englisches Beispiel für Rekursion.
quelle
Rekursion ist im grundlegendsten Sinne der Informatik eine Funktion, die sich selbst nennt. Angenommen, Sie haben eine verknüpfte Listenstruktur:
Und Sie möchten herausfinden, wie lang eine verknüpfte Liste ist. Dies können Sie mit Rekursion tun:
(Dies könnte natürlich auch mit einer for-Schleife erfolgen, ist aber zur Veranschaulichung des Konzepts nützlich.)
quelle
length(list->next)
muss immer noch zu zurückkehren,length(list)
damit letzterer 1 zum Ergebnis hinzufügen kann. Wurde geschrieben, um die bisherige Länge weiterzugeben, konnten wir nur dann vergessen, dass der Anrufer existierte. Wieint length(const Node* list, int count=0) { return (!list) ? count : length(list->next, count + 1); }
.Immer wenn sich eine Funktion selbst aufruft und eine Schleife erstellt, ist dies eine Rekursion. Wie bei allem gibt es gute und schlechte Verwendungszwecke für die Rekursion.
Das einfachste Beispiel ist die Schwanzrekursion, bei der die allerletzte Zeile der Funktion ein Aufruf an sich selbst ist:
Dies ist jedoch ein lahmes, fast sinnloses Beispiel, da es leicht durch eine effizientere Iteration ersetzt werden kann. Schließlich leidet die Rekursion unter dem Funktionsaufruf-Overhead, der im obigen Beispiel im Vergleich zu der Operation innerhalb der Funktion selbst erheblich sein kann.
Der ganze Grund, eher eine Rekursion als eine Iteration durchzuführen, sollte darin bestehen, den Aufrufstapel zu nutzen, um einige clevere Dinge zu tun. Wenn Sie beispielsweise eine Funktion mehrmals mit unterschiedlichen Parametern innerhalb derselben Schleife aufrufen, können Sie auf diese Weise eine Verzweigung durchführen . Ein klassisches Beispiel ist das Sierpinski-Dreieck .
Sie können eine davon ganz einfach mit Rekursion zeichnen, wobei der Aufrufstapel in drei Richtungen verzweigt:
Wenn Sie versuchen, dasselbe mit der Iteration zu tun, werden Sie wahrscheinlich viel mehr Code benötigen, um dies zu erreichen.
Andere häufige Anwendungsfälle können das Durchlaufen von Hierarchien sein, z. B. Website-Crawler, Verzeichnisvergleiche usw.
Fazit
In der Praxis ist die Rekursion am sinnvollsten, wenn Sie eine iterative Verzweigung benötigen.
quelle
Rekursion ist eine Methode zur Lösung von Problemen, die auf der Teilungs- und Eroberungsmentalität basieren. Die Grundidee ist, dass Sie das ursprüngliche Problem in kleinere (leichter zu lösende) Instanzen von sich selbst aufteilen, diese kleineren Instanzen lösen (normalerweise mit demselben Algorithmus erneut) und sie dann wieder zu der endgültigen Lösung zusammensetzen.
Das kanonische Beispiel ist eine Routine zum Erzeugen des Faktors von n. Das Faktor von n wird berechnet, indem alle Zahlen zwischen 1 und n multipliziert werden. Eine iterative Lösung in C # sieht folgendermaßen aus:
Die iterative Lösung ist nicht überraschend und sollte für jeden, der mit C # vertraut ist, sinnvoll sein.
Die rekursive Lösung wird gefunden, indem erkannt wird, dass das n-te Faktor n * Fakt (n-1) ist. Oder anders ausgedrückt: Wenn Sie wissen, was eine bestimmte Faktorzahl ist, können Sie die nächste berechnen. Hier ist die rekursive Lösung in C #:
Der erste Teil dieser Funktion wird als Basisfall (oder manchmal als Schutzklausel) bezeichnet und verhindert, dass der Algorithmus für immer ausgeführt wird. Es wird nur der Wert 1 zurückgegeben, wenn die Funktion mit einem Wert von 1 oder weniger aufgerufen wird. Der zweite Teil ist interessanter und wird als rekursiver Schritt bezeichnet . Hier rufen wir dieselbe Methode mit einem leicht modifizierten Parameter auf (wir dekrementieren ihn um 1) und multiplizieren dann das Ergebnis mit unserer Kopie von n.
Bei der ersten Begegnung kann dies verwirrend sein. Daher ist es lehrreich zu untersuchen, wie es beim Ausführen funktioniert. Stellen Sie sich vor, wir nennen FactRec (5). Wir treten in die Routine ein, werden nicht vom Basisfall erfasst und landen so:
Wenn wir die Methode mit dem Parameter 4 erneut eingeben, werden wir erneut nicht durch die Guard-Klausel gestoppt und landen bei:
Wenn wir diesen Rückgabewert durch den oben angegebenen Rückgabewert ersetzen, erhalten wir
Dies sollte Ihnen einen Hinweis darauf geben, wie die endgültige Lösung gefunden wird, damit wir jeden Schritt auf dem Weg nach unten schnell verfolgen und zeigen können:
Diese endgültige Ersetzung erfolgt, wenn der Basisfall ausgelöst wird. An dieser Stelle müssen wir eine einfache algrebraische Formel lösen, die in erster Linie direkt der Definition von Fakultäten entspricht.
Es ist aufschlussreich zu beachten, dass bei jedem Aufruf der Methode entweder ein Basisfall ausgelöst wird oder dieselbe Methode aufgerufen wird, bei der die Parameter näher an einem Basisfall liegen (häufig als rekursiver Aufruf bezeichnet). Ist dies nicht der Fall, wird die Methode für immer ausgeführt.
quelle
FactRec()
vonn
vor der Rückkehr mit multipliziert werden .Rekursion löst ein Problem mit einer Funktion, die sich selbst aufruft. Ein gutes Beispiel hierfür ist eine Fakultätsfunktion. Factorial ist ein mathematisches Problem, bei dem die Fakultät 5 beispielsweise 5 * 4 * 3 * 2 * 1 ist. Diese Funktion löst dies in C # für positive ganze Zahlen (nicht getestet - möglicherweise liegt ein Fehler vor).
quelle
Rekursion bezieht sich auf eine Methode, die ein Problem löst, indem eine kleinere Version des Problems gelöst und dieses Ergebnis sowie eine andere Berechnung verwendet wird, um die Antwort auf das ursprüngliche Problem zu formulieren. Oft löst die Methode beim Lösen der kleineren Version eine noch kleinere Version des Problems usw., bis ein "Basisfall" erreicht ist, dessen Lösung trivial ist.
Um beispielsweise eine Fakultät für die Zahl zu berechnen
X
, kann man sie als darstellenX times the factorial of X-1
. Somit "rekursiert" die Methode, um die Fakultät von zu findenX-1
, und multipliziert dann alles, was sie erhalten hatX
, um eine endgültige Antwort zu geben. Um die Fakultät von zu finden, wird natürlichX-1
zuerst die Fakultät berechnetX-2
und so weiter. Der Basisfall wäre, wennX
0 oder 1 ist. In diesem Fall kann er1
seitdem zurückkehren0! = 1! = 1
.quelle
Betrachten Sie ein altes, bekanntes Problem :
Die Definition von gcd ist überraschend einfach:
Dabei ist mod der Modulo-Operator ( dh der Rest nach der Ganzzahldivision).
Im Englischen besagt diese Definition, dass der größte gemeinsame Teiler einer Zahl und Null diese Zahl ist und der größte gemeinsame Teiler zweier Zahlen m und n der größte gemeinsame Teiler von n und der Rest nach Division von m durch n ist .
Wenn Sie wissen möchten, warum dies funktioniert, lesen Sie den Wikipedia-Artikel zum euklidischen Algorithmus .
Berechnen wir als Beispiel gcd (10, 8). Jeder Schritt ist gleich dem unmittelbar davor:
Im ersten Schritt ist 8 nicht gleich Null, daher gilt der zweite Teil der Definition. 10 mod 8 = 2, weil 8 einmal mit einem Rest von 2 in 10 geht. In Schritt 3 gilt der zweite Teil erneut, diesmal jedoch 8 mod 2 = 0, weil 2 8 ohne Rest teilt. In Schritt 5 ist das zweite Argument 0, daher lautet die Antwort 2.
Haben Sie bemerkt, dass gcd sowohl auf der linken als auch auf der rechten Seite des Gleichheitszeichens angezeigt wird? Ein Mathematiker würde sagen, dass diese Definition rekursiv ist, da der Ausdruck, den Sie definieren, innerhalb seiner Definition wiederkehrt .
Rekursive Definitionen sind in der Regel elegant. Eine rekursive Definition für die Summe einer Liste lautet beispielsweise
Dabei
head
ist das erste Element in einer Liste undtail
der Rest der Liste. Beachten Sie, dasssum
sich die Definition am Ende wiederholt.Vielleicht möchten Sie stattdessen den Maximalwert in einer Liste bevorzugen:
Sie können die Multiplikation nicht negativer Ganzzahlen rekursiv definieren, um daraus eine Reihe von Additionen zu machen:
Wenn das Umwandeln der Multiplikation in eine Reihe von Additionen keinen Sinn ergibt, erweitern Sie einige einfache Beispiele, um zu sehen, wie es funktioniert.
Zusammenführungssortierung hat eine schöne rekursive Definition:
Rekursive Definitionen gibt es überall, wenn Sie wissen, wonach Sie suchen müssen. Beachten Sie, dass alle diese Definitionen sehr einfache Basisfälle haben, z gcd (m, 0) = m. Die rekursiven Fälle lösen das Problem auf, um zu den einfachen Antworten zu gelangen.
Mit diesem Verständnis können Sie jetzt die anderen Algorithmen in Wikipedia's Artikel über Rekursion schätzen !
quelle
Das kanonische Beispiel ist die Fakultät, die aussieht wie:
Im Allgemeinen ist die Rekursion nicht unbedingt schnell (der Overhead für Funktionsaufrufe ist in der Regel hoch, da rekursive Funktionen in der Regel klein sind (siehe oben)) und kann unter einigen Problemen leiden (Stapelüberlauf jemand?). Einige sagen, dass es in nicht trivialen Fällen schwierig ist, „richtig“ zu machen, aber ich kaufe mir das nicht wirklich ein. In einigen Situationen ist Rekursion am sinnvollsten und die eleganteste und klarste Art, eine bestimmte Funktion zu schreiben. Es sollte beachtet werden, dass einige Sprachen rekursive Lösungen bevorzugen und diese viel stärker optimieren (LISP fällt mir ein).
quelle
Eine rekursive Funktion ruft sich selbst auf. Der häufigste Grund, warum ich es verwendet habe, ist das Durchqueren einer Baumstruktur. Wenn ich beispielsweise eine TreeView mit Kontrollkästchen habe (denken Sie an die Installation eines neuen Programms, Seite "Zu installierende Funktionen auswählen"), möchte ich möglicherweise eine Schaltfläche "Alle überprüfen", die ungefähr so aussieht (Pseudocode):
Sie können also sehen, dass checkRecursively zuerst den Knoten überprüft, an den es übergeben wurde, und sich dann selbst für jedes untergeordnete Element dieses Knotens aufruft.
Sie müssen bei der Rekursion etwas vorsichtig sein. Wenn Sie in eine unendliche rekursive Schleife geraten, erhalten Sie eine Stapelüberlauf-Ausnahme :)
Ich kann mir keinen Grund vorstellen, warum die Leute es nicht benutzen sollten, wenn es angebracht ist. Es ist unter bestimmten Umständen nützlich und unter anderen nicht.
Ich denke, weil es eine interessante Technik ist, verwenden einige Programmierer sie möglicherweise häufiger als sie sollten, ohne es wirklich zu rechtfertigen. Dies hat der Rekursion in einigen Kreisen einen schlechten Ruf gegeben.
quelle
Rekursion ist ein Ausdruck, der direkt oder indirekt auf sich selbst verweist.
Betrachten Sie rekursive Akronyme als einfaches Beispiel:
Weitere Beispiele auf Wikipedia
quelle
Rekursion funktioniert am besten mit dem, was ich gerne als "fraktale Probleme" bezeichne, bei denen es sich um eine große Sache handelt, die aus kleineren Versionen dieser großen Sache besteht, von denen jede eine noch kleinere Version der großen Sache ist, und so weiter. Wenn Sie jemals etwas wie einen Baum oder verschachtelte identische Strukturen durchqueren oder durchsuchen müssen, haben Sie ein Problem, das ein guter Kandidat für eine Rekursion sein könnte.
Menschen vermeiden eine Rekursion aus einer Reihe von Gründen:
Die meisten Leute (ich eingeschlossen) schneiden ihre Programmierzähne bei prozeduraler oder objektorientierter Programmierung im Gegensatz zur funktionalen Programmierung. Für solche Menschen fühlt sich der iterative Ansatz (normalerweise unter Verwendung von Schleifen) natürlicher an.
Denjenigen von uns, die sich bei der prozeduralen oder objektorientierten Programmierung die Zähne schneiden, wurde oft gesagt, dass sie eine Rekursion vermeiden sollen, weil sie fehleranfällig ist.
Uns wird oft gesagt, dass die Rekursion langsam ist. Das wiederholte Aufrufen und Zurückkehren von einer Routine erfordert viel Stapeln und Poppen des Stapels, was langsamer als das Schleifen ist. Ich denke, einige Sprachen handhaben dies besser als andere, und diese Sprachen sind höchstwahrscheinlich nicht diejenigen, bei denen das vorherrschende Paradigma prozedural oder objektorientiert ist.
Für mindestens ein paar Programmiersprachen, die ich verwendet habe, erinnere ich mich an Empfehlungen, keine Rekursion zu verwenden, wenn sie eine bestimmte Tiefe überschreitet, weil ihr Stapel nicht so tief ist.
quelle
Eine rekursive Anweisung ist eine Anweisung, in der Sie den Prozess definieren, was als Nächstes zu tun ist, als Kombination der Eingaben und was Sie bereits getan haben.
Nehmen Sie zum Beispiel Fakultät:
Aber es ist leicht zu erkennen, dass Fakultät (6) auch ist:
Also allgemein:
Das Schwierige an der Rekursion ist natürlich, dass es einen Ausgangspunkt geben muss, wenn Sie Dinge in Bezug auf das definieren möchten, was Sie bereits getan haben.
In diesem Beispiel machen wir nur einen Sonderfall, indem wir Fakultät (1) = 1 definieren.
Jetzt sehen wir es von unten nach oben:
Da wir Fakultät (1) = 1 definiert haben, erreichen wir den "Boden".
Im Allgemeinen bestehen rekursive Prozeduren aus zwei Teilen:
1) Der rekursive Teil, der eine Prozedur in Bezug auf neue Eingaben definiert, kombiniert mit dem, was Sie über dieselbe Prozedur "bereits getan" haben. (dh
factorial(n) = n*factorial(n-1)
)2) Ein Basisteil, das sicherstellt, dass sich der Prozess nicht für immer wiederholt, indem es ihm einen Startplatz gibt (dh
factorial(1) = 1
)Es kann etwas verwirrend sein, zuerst den Kopf herumzukriegen, aber schauen Sie sich nur ein paar Beispiele an und alles sollte zusammenkommen. Wenn Sie das Konzept besser verstehen möchten, studieren Sie die mathematische Induktion. Beachten Sie außerdem, dass einige Sprachen für rekursive Aufrufe optimiert sind, andere jedoch nicht. Es ist ziemlich einfach, wahnsinnig langsame rekursive Funktionen zu erstellen, wenn Sie nicht vorsichtig sind, aber es gibt auch Techniken, um sie in den meisten Fällen performant zu machen.
Hoffe das hilft...
quelle
Ich mag diese Definition:
In der Rekursion löst eine Routine einen kleinen Teil eines Problems selbst, teilt das Problem in kleinere Teile und ruft sich dann selbst auf, um jedes der kleineren Teile zu lösen.
Ich mag auch Steve McConnells Diskussion über Rekursion in Code Complete, wo er die Beispiele kritisiert, die in Informatikbüchern über Rekursion verwendet werden.
Ich dachte, dies sei ein sehr interessanter Punkt und könnte ein Grund sein, warum Rekursion oft missverstanden wird.
EDIT: Dies war keine Auseinandersetzung mit Davs Antwort - ich hatte diese Antwort nicht gesehen, als ich sie gepostet habe
quelle
1.) Eine Methode ist rekursiv, wenn sie sich selbst aufrufen kann; entweder direkt:
oder indirekt:
2.) Wann wird die Rekursion verwendet?
3.) Menschen verwenden Rekursion nur, wenn das Schreiben von iterativem Code sehr komplex ist. Beispielsweise können Baumdurchquerungstechniken wie Vorbestellung und Nachbestellung sowohl iterativ als auch rekursiv ausgeführt werden. Aber normalerweise verwenden wir wegen seiner Einfachheit rekursiv.
quelle
Hier ist ein einfaches Beispiel: Wie viele Elemente in einer Menge. (Es gibt bessere Möglichkeiten, Dinge zu zählen, aber dies ist ein schönes einfaches rekursives Beispiel.)
Erstens brauchen wir zwei Regeln:
Angenommen, Sie haben einen Satz wie diesen: [xxx]. Zählen wir, wie viele Elemente es gibt.
Wir können dies darstellen als:
Wenn Sie eine rekursive Lösung anwenden, haben Sie normalerweise mindestens zwei Regeln:
Wenn wir das Obige in Pseudocode übersetzen, erhalten wir:
Es gibt viel nützlichere Beispiele (zum Beispiel das Durchqueren eines Baumes), die sicher andere Leute behandeln werden.
quelle
Nun, das ist eine ziemlich anständige Definition, die Sie haben. Und Wikipedia hat auch eine gute Definition. Also werde ich eine weitere (wahrscheinlich schlechtere) Definition für Sie hinzufügen.
Wenn Leute von "Rekursion" sprechen, sprechen sie normalerweise über eine Funktion, die sie geschrieben haben und die sich wiederholt aufruft, bis sie mit ihrer Arbeit fertig ist. Rekursion kann hilfreich sein, wenn Hierarchien in Datenstrukturen durchlaufen werden.
quelle
Ein Beispiel: Eine rekursive Definition einer Treppe lautet: Eine Treppe besteht aus: - einer einzelnen Stufe und einer Treppe (Rekursion) - oder nur einer einzelnen Stufe (Beendigung)
quelle
Um auf ein gelöstes Problem zurückzugreifen: Tun Sie nichts, Sie sind fertig.
So wiederholen Sie ein offenes Problem: Führen Sie den nächsten Schritt aus und wiederholen Sie den Rest.
quelle
Im Klartext: Angenommen, Sie können drei Dinge tun:
Sie haben viele Äpfel vor sich auf einem Tisch und möchten wissen, wie viele Äpfel es gibt.
Der Vorgang, dasselbe zu wiederholen, bis Sie fertig sind, wird als Rekursion bezeichnet.
Ich hoffe, dies ist die "einfache englische" Antwort, die Sie suchen!
quelle
Eine rekursive Funktion ist eine Funktion, die einen Aufruf an sich selbst enthält. Eine rekursive Struktur ist eine Struktur, die eine Instanz von sich selbst enthält. Sie können beide als rekursive Klasse kombinieren. Der Schlüsselteil eines rekursiven Elements besteht darin, dass es eine Instanz / einen Aufruf von sich selbst enthält.
Betrachten Sie zwei Spiegel, die sich gegenüberstehen. Wir haben den ordentlichen Unendlichkeitseffekt gesehen, den sie machen. Jede Reflexion ist eine Instanz eines Spiegels, die in einer anderen Instanz eines Spiegels usw. enthalten ist. Der Spiegel, der eine Reflexion von sich selbst enthält, ist eine Rekursion.
Ein binärer Suchbaum ist ein gutes Programmierbeispiel für Rekursion. Die Struktur ist rekursiv, wobei jeder Knoten 2 Instanzen eines Knotens enthält. Funktionen, die an einem binären Suchbaum arbeiten, sind ebenfalls rekursiv.
quelle
Dies ist eine alte Frage, aber ich möchte eine Antwort aus logistischer Sicht hinzufügen (dh nicht aus Sicht der Algorithmuskorrektheit oder Leistung).
Ich benutze Java für die Arbeit und Java unterstützt keine verschachtelten Funktionen. Wenn ich eine Rekursion durchführen möchte, muss ich möglicherweise eine externe Funktion definieren (die nur existiert, weil mein Code gegen die bürokratische Regel von Java verstößt), oder ich muss den Code möglicherweise komplett umgestalten (was ich wirklich hasse).
Daher vermeide ich häufig eine Rekursion und verwende stattdessen eine Stapeloperation, da die Rekursion selbst im Wesentlichen eine Stapeloperation ist.
quelle
Sie möchten es immer dann verwenden, wenn Sie eine Baumstruktur haben. Es ist sehr nützlich beim Lesen von XML.
quelle
Rekursion, wie sie für die Programmierung gilt, ruft im Grunde genommen eine Funktion aus ihrer eigenen Definition (in sich selbst) mit verschiedenen Parametern auf, um eine Aufgabe zu erfüllen.
quelle
"Wenn ich einen Hammer habe, lass alles wie einen Nagel aussehen."
Rekursion ist eine Problemlösungsstrategie für große Probleme, bei der bei jedem Schritt jedes Mal mit demselben Hammer "2 kleine Dinge in eine größere Sache verwandelt werden".
Beispiel
Angenommen, Ihr Schreibtisch ist mit einem unorganisierten Durcheinander von 1024 Papieren bedeckt. Wie macht man mit Rekursion einen ordentlichen, sauberen Stapel Papier aus dem Durcheinander?
Beachten Sie, dass dies ziemlich intuitiv ist, abgesehen davon, dass alles gezählt wird (was nicht unbedingt erforderlich ist). In Wirklichkeit könnten Sie nicht bis zu 1-Blatt-Stapeln gehen, aber Sie könnten und es würde immer noch funktionieren. Der wichtige Teil ist der Hammer: Mit Ihren Armen können Sie immer einen Stapel übereinander legen, um einen größeren Stapel zu erhalten, und es spielt keine Rolle (innerhalb eines angemessenen Rahmens), wie groß einer der Stapel ist.
quelle
Rekursion ist der Prozess, bei dem ein Methodenaufruf selbst ausgeführt wird, um eine bestimmte Aufgabe ausführen zu können. Es reduziert die Redundanz des Codes. Die meisten rekursiven Funktionen oder Methoden müssen eine Bedingung haben, um den rekursiven Aufruf zu unterbrechen, dh zu verhindern, dass er sich selbst aufruft, wenn eine Bedingung erfüllt ist - dies verhindert die Erstellung einer Endlosschleife. Nicht alle Funktionen können rekursiv verwendet werden.
quelle
Hey, tut mir leid, wenn meine Meinung mit jemandem übereinstimmt. Ich versuche nur, die Rekursion in einfachem Englisch zu erklären.
Angenommen, Sie haben drei Manager - Jack, John und Morgan. Jack verwaltet zwei Programmierer, John - 3 und Morgan - 5. Sie geben jedem Manager 300 $ und möchten wissen, was es kosten würde. Die Antwort liegt auf der Hand - aber was ist, wenn zwei von Morgans Mitarbeitern auch Manager sind?
HIER kommt die Rekursion. Sie beginnen am Anfang der Hierarchie. Die sommerlichen Kosten betragen 0 $. Sie beginnen mit Jack. Überprüfen Sie dann, ob er Manager als Angestellte hat. Wenn Sie feststellen, dass dies der Fall ist, überprüfen Sie, ob Manager als Mitarbeiter vorhanden sind, und so weiter. Fügen Sie 300 $ zu den sommerlichen Kosten hinzu, wenn Sie einen Manager finden. Wenn Sie mit Jack fertig sind, gehen Sie zu John, seinen Mitarbeitern und dann zu Morgan.
Sie werden nie wissen, wie viele Zyklen Sie durchlaufen werden, bevor Sie eine Antwort erhalten, obwohl Sie wissen, wie viele Manager Sie haben und wie viel Budget Sie ausgeben können.
Rekursion ist ein Baum mit Zweigen und Blättern, Eltern und Kinder genannt. Wenn Sie einen Rekursionsalgorithmus verwenden, erstellen Sie mehr oder weniger bewusst einen Baum aus den Daten.
quelle
Rekursion bedeutet im Klartext, etwas immer wieder zu wiederholen.
Bei der Programmierung besteht ein Beispiel darin, die Funktion in sich selbst aufzurufen.
Schauen Sie sich das folgende Beispiel für die Berechnung der Fakultät einer Zahl an:
quelle
Jeder Algorithmus weist eine strukturelle Rekursion für einen Datentyp auf, wenn er im Wesentlichen aus einer switch-Anweisung mit einem Fall für jeden Fall des Datentyps besteht.
Zum Beispiel, wenn Sie an einem Typ arbeiten
Ein struktureller rekursiver Algorithmus hätte die Form
Dies ist wirklich der naheliegendste Weg, einen Algorithmus zu schreiben, der an einer Datenstruktur arbeitet.
Wenn Sie sich nun die ganzen Zahlen (also die natürlichen Zahlen) ansehen, die mit den Peano-Axiomen definiert wurden
Sie sehen, dass ein struktureller rekursiver Algorithmus für ganze Zahlen so aussieht
Die zu bekannte Fakultätsfunktion ist das trivialste Beispiel für diese Form.
quelle
Funktionsaufruf selbst oder eigene Definition verwenden.
quelle