Rekursion (Informatik)
Im Informatik, Rekursion ist eine Methode zur Lösung a Rechenproblem Wo die Lösung von Lösungen für kleinere Instanzen des gleichen Problems abhängt.[1][2] Rekursion löst solche rekursive Probleme durch die Nutzung Funktionen Das ruft sich aus ihrem eigenen Code aus. Der Ansatz kann auf viele Arten von Problemen angewendet werden, und die Rekursion ist eine der zentralen Ideen der Informatik.[3]
Die Macht der Rekursion liegt offensichtlich in der Möglichkeit, einen unendlichen Satz von Objekten durch eine endliche Aussage zu definieren. Auf die gleiche Weise kann eine unendliche Anzahl von Berechnungen durch ein endliches rekursives Programm beschrieben werden, auch wenn dieses Programm keine explizite Wiederholungen enthält.
-Niklaus Wirth, Algorithmen + Datenstrukturen = Programme, 1976[4]
Meiste Computer Programmiersprachen Unterstützen Sie die Rekursion, indem Sie eine Funktion ermöglichen, sich von seinem eigenen Code aus aufzurufen. Etwas Funktionelle Programmierung Sprachen (zum Beispiel, Clojure)[5] Definieren Sie keine Schleifenkonstrukte, sondern verlassen Sie sich ausschließlich auf eine Rekursion, um wiederholt Code aufzurufen. Es ist bewiesen in Computerbarkeitstheorie dass diese nur rekursiven Sprachen sind Turing vollständig; Dies bedeutet, dass sie genauso leistungsfähig sind (sie können verwendet werden, um die gleichen Probleme zu lösen) wie Imperative Sprachen basierend auf Kontrollstrukturen wie z. while
und for
.
Das wiederholte Aufrufen einer Funktion von in sich selbst kann die verursachen Rufen Sie Stack an Eine Größe zu haben, die der Summe der Eingangsgrößen aller beteiligten Anrufe entspricht. Daraus folgt, dass bei Problemen, die durch Iteration leicht gelöst werden können, im Allgemeinen geringer ist effizientund für große Probleme ist es von grundlegender Bedeutung, Optimierungstechniken wie z. Schwanzanruf Optimierung.
Rekursive Funktionen und Algorithmen
Eine gemeinsame Algorithmus Design Taktik besteht darin, ein Problem in Unterprobleme des gleichen Typs wie das Original zu unterteilen, diese Unterprobleme zu lösen und die Ergebnisse zu kombinieren. Dies wird oft als die bezeichnet Divide-and-Conquer-Methode; in Kombination mit einem Nachschlagwerk Dies speichert die Ergebnisse zuvor gelöster Unterprobleme (um sie wiederholt zu lösen und zusätzliche Berechnungszeit zu entstehen), kann es als bezeichnet werden Dynamische Programmierung oder Memoisierung.
Basisfall
Eine rekursive Funktionsdefinition hat eine oder mehrere Basisfälle, Bedeutung Eingaben (n), für die die Funktion ein Ergebnis erzeugt trivial (ohne wiederkehrend) und eine oder mehrere rekursive Fälle, was bedeutet Eingaben, für die das Programm wiederholt wird (nennt sich selbst). Zum Beispiel die Fakultät Funktion kann durch die Gleichungen rekursiv definiert werden 0! = 1 und für alle n > 0, n! = n(n - 1)!. Keine der beiden Gleichungen selbst ist eine vollständige Definition; Der erste ist der Basisfall, und der zweite ist der rekursive Fall. Da der Basisfall die Rekursionskette bricht, wird er manchmal auch als "Terminierfall" bezeichnet.
Die Aufgabe der rekursiven Fälle kann als Aufschlüsselung komplexer Eingaben in einfachere Aufschlüsse angesehen werden. In einer ordnungsgemäß gestalteten rekursiven Funktion muss das Eingabeproblem so vereinfacht werden, dass der Basisfall letztendlich erreicht werden muss. (Funktionen, die unter normalen Umständen nicht enden sollen - zum Beispiel einige System- und Serverprozesse- Ist eine Ausnahme davon.) Vernachlässigung, einen Basisfall zu schreiben oder fälschlicherweise zu testen, kann eine verursachen Endlosschleife.
Für einige Funktionen (z. B. eine, die das berechnet Serie zum e = 1/0! + 1/1! + 1/2! + 1/3! + ...) Es gibt keinen offensichtlichen Basisfall durch die Eingabedaten; denn diese können a hinzufügen Parameter (wie beispielsweise die Anzahl der zu fügigen Begriffe in unserem Serienbeispiel), um ein "Stoppkriterium" bereitzustellen, das den Basisfall festlegt. Ein solches Beispiel wird natürlicher behandelt von Korecursion,[wie?] wo aufeinanderfolgende Begriffe der Ausgabe die Teilsummen sind; Dies kann durch Verwendung des Indexierungsparameters in eine Rekursion konvertiert werden, um zu sagen: "Berechnen Sie die nTH Begriff (nDie Teilsumme) ".
Rekursive Datentypen
Viele Computerprogramme muss eine willkürlich große Menge von verarbeiten oder erzeugen Daten. Rekursion ist eine Technik zur Darstellung von Daten, deren genaue Größe dem unbekannt ist Programmierer: Der Programmierer kann diese Daten mit a angeben selbstreferenziell Definition. Es gibt zwei Arten von selbstreferenziellen Definitionen: induktiv und koinduktiv Definitionen.
Induktiv definierte Daten
Eine induktiv definierte rekursive Datendarstellung ist eine, die angibt, wie Sie Instanzen der Daten konstruieren. Zum Beispiel, verlinkte Listen kann induktiv definiert werden (hier, verwenden Haskell Syntax):
Daten ListofStrings = Leere Liste | Nachteile Saite ListofStrings
Der obige Code gibt eine Liste von Zeichenfolgen an, die entweder leer sind, oder eine Struktur, die eine Zeichenfolge und eine Liste von Zeichenfolgen enthält. Die Selbstreferenz in der Definition ermöglicht die Konstruktion von Listen einer (endlichen) Anzahl von Zeichenfolgen.
Ein weiteres Beispiel für induktiv Definition ist der natürliche Zahlen (oder positiv Ganzzahlen):
Eine natürliche Zahl ist entweder 1 oder n+1, wobei N eine natürliche Zahl ist.
Ähnlich rekursiv Definitionen werden oft verwendet, um die Struktur von zu modellieren Ausdrücke und Aussagen in Programmiersprachen. Sprachdesigner drücken häufig Grammatiken in einer Syntax aus, z. Backus -Naur -Form; Hier ist eine solche Grammatik für eine einfache Sprache arithmetischer Ausdrücke mit Multiplikation und Zugabe:
<Expr> :: = <Nummer> | (<Expr> * <Expr>) | (<Expr> + <Expr>))
Dies besagt, dass ein Ausdruck entweder eine Zahl, ein Produkt von zwei Ausdrücken oder eine Summe von zwei Ausdrücken ist. Indem die Grammatik rekursiv auf Ausdrücke in der zweiten und dritten Zeile bezieht, erlaubt sie willkürlich komplizierte arithmetische Ausdrücke wie z. (5 * ((3 * 6) + 8))
, mit mehr als einem Produkt oder einer Summenoperation in einem einzigen Ausdruck.
Koinduktiv definierte Daten und Corecursion
Eine Koinduktionsdatendefinition ist eine, die die Operationen angibt, die für ein Datenstück ausgeführt werden können. Typischerweise werden selbstreferenzielle koinduktive Definitionen für Datenstrukturen von unendlicher Größe verwendet.
Eine koinduktive Definition von unendlich Ströme von Saiten, die informell gegeben sind, könnten so aussehen:
Ein Strom von Strings ist ein Objekt, so dass: Kopf (n) eine Zeichenfolge und Schwanz (n) ein Strangstrangs ist.
Dies ist einer induktiven Definition von Stringslisten sehr ähnlich; Der Unterschied besteht darin, dass diese Definition festgelegt hat Accessor Funktionen Kopf
und Schwanz
- und welche Inhalte sein mögen, während die induktive Definition angibt, wie die Struktur erstellt wird und was sie erstellt werden kann.
Corecursion hängt mit der Koinktion zusammen und kann verwendet werden, um bestimmte Instanzen von (möglicherweise) unendlichen Objekten zu berechnen. Als Programmierungstechnik wird es am häufigsten im Kontext von verwendet faul Programmiersprachen und kann der Rekursion vorzuziehen sein, wenn die gewünschte Größe oder Präzision der Ausgabe eines Programms unbekannt ist. In solchen Fällen erfordert das Programm sowohl eine Definition für ein unendlich großes (oder unendlich präzises) Ergebnis als auch einen Mechanismus, um einen endlichen Teil dieses Ergebnisses zu erhalten. Das Problem der Berechnung des ersten n Primzahlen ist eine, die mit einem korezisiven Programm gelöst werden kann (z. hier).
Arten von Rekursion
Einzelne Rekursion und Mehrfachrekursion
Rekursion, die nur eine einzige Selbstreferenz enthält Einzelrekursionwährend eine Rekursion, die mehrere Selbstreferenzen enthält Mehrfachrekursion. Zu den Standardbeispielen für Einzelrekursion gehören List -Traversal, z. Baumtraversal, wie beispielsweise bei der ersten Suche.
Einzelrekursion ist oft viel effizienter als mehrere Rekursion und kann im Allgemeinen durch eine iterative Berechnung ersetzt werden, die in linearer Zeit ausgeführt wird und einen konstanten Raum erfordert. Im Gegensatz dazu kann eine Mehrfachrekursion exponentielles Zeit und Raum erfordern und ist grundlegender rekursiver, ohne dass es ohne explizite Stapel durch Iteration ersetzt werden kann.
Multiple Rekursion kann manchmal in eine einzelne Rekursion (und, falls gewünscht, von dort zur Iteration) umgewandelt werden. Bei der Berechnung der Fibonacci -Sequenz beinhaltet beispielsweise naiv mehrere Iteration, da jeder Wert zwei vorherige Werte erfordert, kann er durch einzelne Rekursion durch Übergabe von zwei aufeinanderfolgenden Werten als Parameter berechnet werden. Dies ist natürlicher als Korecursion, die sich aus den Anfangswerten aufbauen, während zwei aufeinanderfolgende Werte bei jedem Schritt verfolgt werden - siehe Corecursion: Beispiele. Ein ausgefeilteres Beispiel besteht darin, a zu verwenden Binärbaum mit Gewinde, was iterativen Baumtraversal ermöglicht, anstatt mehrere Rekursion.
Indirekte Rekursion
Die meisten grundlegenden Beispiele für Rekursion und die meisten hier vorgestellten Beispiele zeigen Direkte Rekursion, in dem eine Funktion sich selbst nennt. Indirekt Rekursion tritt auf, wenn eine Funktion nicht von selbst, sondern durch eine andere Funktion, die sie (entweder direkt oder indirekt) bezeichnet hat, bezeichnet wird. Zum Beispiel wenn f Anrufe f, Das ist eine direkte Rekursion, aber wenn f Anrufe g welche ruft f, Dann ist das indirekte Rekursion von f. Ketten mit drei oder mehr Funktionen sind möglich; Beispielsweise Funktion 1 Aufrufe Funktion 2, Funktion 2 Aufrufe Funktion 3 und Funktion 3 Aufrufe Funktion 1 erneut.
Die indirekte Rekursion wird auch genannt gegenseitige Rekursion, was ein symmetrischerer Begriff ist, obwohl dies einfach ein Unterschied in der Betonung ist, kein anderer Begriff. Das heißt, wenn f Anrufe g und dann g Anrufe f, was wiederum anruft g Wieder aus der Sicht von f allein, f wird indirekt wiederholt, während aus Sicht von Sicht g allein ist es indirekt wiederholt, während es aus der Sicht beider, f und g werden gegenseitig gegenseitig wiederholt. In ähnlicher Weise kann ein Satz von drei oder mehr Funktionen, die sich gegenseitig aufrufen, als eine Reihe von gegenseitig rekursiven Funktionen bezeichnet werden.
Anonyme Rekursion
Rekursion erfolgt normalerweise, indem eine Funktion explizit mit Namen aufgerufen wird. Eine Rekursion kann jedoch auch durchgeführt werden, indem sie implizit eine Funktion basierend auf dem aktuellen Kontext aufrufen, was besonders nützlich ist für Anonyme Funktionenund ist bekannt als als Anonyme Rekursion.
Strukturelle versus generative Rekursion
Einige Autoren klassifizieren Rekursion entweder als "strukturell" oder "generativ". Die Unterscheidung hängt damit zusammen, wo ein rekursives Verfahren die Daten erhält, an denen es funktioniert, und wie es diese Daten verarbeitet:
[Funktionen, die strukturierte Daten konsumieren] zerlegen ihre Argumente normalerweise in ihre unmittelbaren strukturellen Komponenten und verarbeiten dann diese Komponenten. Wenn eine der unmittelbaren Komponenten zur gleichen Datenklasse wie die Eingabe gehört, ist die Funktion rekursiv. Aus diesem Grund bezeichnen wir diese Funktionen als (strukturell) rekursive Funktionen.
-Fellisen, Findler, Flatt und Krishnaurthi, So entwerfen Sie Programme, 2001[6]
Das definierende Merkmal einer strukturell rekursiven Funktion ist daher, dass das Argument für jeden rekursiven Aufruf der Inhalt eines Feldes der ursprünglichen Eingabe ist. Die strukturelle Rekursion umfasst fast alle Baumtravers, einschließlich XML -Verarbeitung, Binärbaumerstellung und -Suche usw. unter Berücksichtigung der algebraischen Struktur der natürlichen Zahlen (dh eine natürliche Zahl ist entweder Null oder der Nachfolger einer natürlichen Zahl), Funktionen wie als faktorial kann auch als strukturelle rekursion angesehen werden.
Generative Rekursion ist die Alternative:
Viele bekannte rekursive Algorithmen erzeugen aus den angegebenen Daten ein völlig neues Datenstück und wieder auf. Htdp (So entwerfen Sie Programme) bezeichnet diese Art als generative Rekursion. Beispiele für generative Rekursion sind: GCD, schnelle Sorte, binäre Suche, Zusammenführen, sortieren, Newtons Methode, Fraktale, und Adaptive Integration.
-Matthias Fellisen, Erweiterte funktionale Programmierung, 2002[7]
Diese Unterscheidung ist wichtig in Beweiskündigung einer Funktion.
- Alle strukturell rekursiven Funktionen für endlich (induktiv definiert) Datenstrukturen können leicht nachgewiesen werden, über strukturelle Induktion: Intuitiv empfängt jeder rekursive Anruf ein kleineres Eingabedaten, bis ein Basisfall erreicht ist.
- Generativ rekursive Funktionen dagegen im Gegensatz dazu nicht unbedingt kleinere Eingaben in ihre rekursiv Unendliche Schleifen erfordert mehr Pflege. Diese generativ rekursiven Funktionen können häufig als Corecursive -Funktionen interpretiert werden - jeder Schritt generiert die neuen Daten, wie z.
- Bezüglich SchleifenvariantenDie strukturelle Rekursion ist, wenn es eine offensichtliche Schleifenvariante gibt, nämlich Größe oder Komplexität, die endlich beginnt und bei jedem rekursiven Schritt abnimmt.
- Im Gegensatz dazu besteht die generative Rekursion, wenn es keine so offensichtliche Schleifenvariante gibt, und die Beendigung hängt von einer Funktion ab, z.
Umsetzungsfragen
In der tatsächlichen Implementierung und nicht in einer reinen rekursiven Funktion (einzelne Prüfung für Basisfall, ansonsten rekursiver Schritt) können eine Reihe von Modifikationen zum Zwecke der Klarheit oder Effizienz vorgenommen werden. Diese beinhalten:
- Wrapper -Funktion (oben)
- Kurzschluss des Basisfalles, auch bekannt als "Arm's Langlength Rekursion" (unten)
- Hybridalgorithmus (unten) - Wechsel zu einem anderen Algorithmus, sobald die Daten klein genug sind
Auf der Grundlage der Eleganz werden Wrapper-Funktionen im Allgemeinen genehmigt, während die Kurzzeitverkleidung des Basisfalls, insbesondere in der Wissenschaft, verpönt wird. Hybridalgorithmen werden häufig zur Effizienz verwendet, um den Überkopf der Rekursion in kleinen Fällen zu verringern, und die Recursion der Armslänge ist ein Sonderfall davon.
Wrapper -Funktion
A Wrapper -Funktion ist eine Funktion, die direkt aufgerufen wird, aber sich nicht selbst wiederholt, sondern auf eine separate Hilfsfunktion aufzurufen, die tatsächlich die Rekursion durchführt.
Wrapper -Funktionen können verwendet werden, um Parameter zu validieren (so dass die rekursive Funktion diese überspringen kann), die Initialisierung durchführen (Speicher zuweisen, Variablen initialisieren), insbesondere für Hilfsvariablen wie "Recursion -Ebene" oder partielle Berechnungen für Memoisierung, und behandeln Sie Ausnahmen und Fehler. In Sprachen, die unterstützen verschachtelte FunktionenDie Hilfsfunktion kann innerhalb der Wrapper -Funktion verschachtelt werden und verwenden einen gemeinsamen Bereich. In Ermangelung von verschachtelten Funktionen sind Hilfsfunktionen stattdessen eine separate Funktion, wenn möglich privat (da sie nicht direkt aufgerufen werden), und Informationen werden mit der Wrapper -Funktion mithilfe von Verwendung geteilt Pass-by-Reference.
Kurzschluss des Basisfalles
Gewöhnliche Rekursion | Kurzschlussrekursion |
---|---|
int FAC1(int n) { wenn (n <= 0) Rückkehr 1; anders Rückkehr FAC1(n-1)*n; } | statisch int FAC2(int n) { // Assert (n> = 2); wenn (n == 2) Rückkehr 2; anders Rückkehr FAC2(n-1)*n; } int FAC2Wrapper(int n) { wenn (n <= 1) Rückkehr 1; anders Rückkehr FAC2(n); } |
Kurzschluss des Basisfalls, auch bekannt als Armslänge Rekursion, besteht aus der Überprüfung des Basisfalles Vor Einen rekursiven Anruf tätigen - d. H. Überprüfen Sie, ob der nächste Anruf der Basisfall ist, anstatt anzurufen und dann nach dem Basisfall zu überprüfen. Die Kurzschlüsse erfolgt insbesondere aus Effizienzgründen, um den Aufwand eines Funktionsaufrufs zu vermeiden, der sofort zurückgibt. Beachten Sie, dass der Basisfall bereits auf (unmittelbar vor dem rekursiven Schritt) überprüft wurde, er nicht auf separat überprüft werden muss, aber man muss eine Wrapper -Funktion für den Fall verwenden, wenn die Gesamtrekursion mit dem Basisfall beginnt selbst. In der faktoriellen Funktion beispielsweise ist der Basisfall ordnungsgemäß 0! = 1, während sofort 1 für 1 zurückkehrt! ist ein Kurzschluss und kann 0 verpassen; Dies kann durch eine Wrapper -Funktion gemindert werden. Die Box zeigt C Code zu Verknüpfungsfaktorenfällen 0 und 1.
Die Kurzschließung ist in erster Linie ein Problem, wenn viele Basisfälle auftreten, wie z. O(n) Algorithmen; Dies ist unten für eine Tiefensuche dargestellt. Die Kurzschlüsse an einem Baum entspricht der Berücksichtigung eines Blattes (nicht leerer Knoten ohne Kinder) als Basisfall, anstatt einen leeren Knoten als Basisfall zu betrachten. Wenn es nur einen einzelnen Basisfall gibt, z. O(1) Ersparnisse.
Konzeptionell kann in Betracht gezogen werden, dass die Kurzzeitbeschäftigung entweder denselben Basisfall und den rekursiven Schritt hat und den Basisfall nur vor der Rekursion überprüft, oder es kann als einen anderen Basisfall (ein Schritt aus dem Standard-Basisfall entfernt) und a angesehen werden. Komplexer rekursiver Schritt, nämlich "gültig prüfen, dann wieder aufzunehmen", wie bei der Betrachtung von Blattknoten anstelle von Nullknoten als Basisfälle in einem Baum. Da die Kurzschlüsse im Vergleich zur klaren Trennung von Basisfall und einem rekursiven Schritt in der Standardrekursion einen komplizierteren Fluss aufweist, wird dies häufig als schlechter Stil angesehen, insbesondere in der Wissenschaft.[8]
Tiefe-First-Suche
Ein grundlegendes Beispiel für kurzfristige Kurzschlüsse ist in angegeben Tiefe-First-Suche (Dfs) eines binären Baumes; sehen Binärbäume Abschnitt für eine rekursive Diskussion.
Der Standard -rekursive Algorithmus für ein DFS lautet:
- Basisfall: Wenn der aktuelle Knoten null ist, geben Sie false zurück
- Rekursive Schritt: Ansonsten prüfen Sie den Wert des aktuellen Knotens, geben Sie true zurück, wenn Sie übereinstimmen, andernfalls reduzieren Sie sie bei Kindern
Im Kurzschluss ist dies stattdessen:
- Überprüfen Sie den Wert des aktuellen Knotens und geben Sie true zurück, wenn Sie übereinstimmen.
- Andernfalls wiederholen Sie bei Kindern, wenn nicht Null.
In Bezug auf die Standardschritte wird die Basisfallprüfung bewegt Vor der rekursive Schritt. Alternativ können diese als unterschiedliche Form von Basisfall bzw. rekursiven Schritt angesehen werden. Beachten Sie, dass dies eine Wrapper -Funktion erfordert, um den Fall zu verarbeiten, wenn der Baum selbst leer ist (Rootknoten ist null).
Im Fall von a Perfekter binärer Baum der Höhe h, da sind 2h+1–1 Knoten und 2h+1 Nullzeiger als Kinder (2 für jedes der 2h Blätter), so dass die Kurzschlüsse die Anzahl der Funktionsaufrufe im schlimmsten Fall halbiert.
In C kann der Standard -rekursive Algorithmus implementiert werden als:
bool Tree_contains(Struktur Knoten *Tree_Node, int i) { wenn (Tree_Node == NULL) Rückkehr FALSCH; // Basisfall anders wenn (Tree_Node->Daten == i) Rückkehr Stimmt; anders Rückkehr Tree_contains(Tree_Node->links, i) || Tree_contains(Tree_Node->Rechts, i); }
Der Kurzschlussalgorithmus kann implementiert werden als:
// Wrapper -Funktion für den leeren Baum verarbeitet bool Tree_contains(Struktur Knoten *Tree_Node, int i) { wenn (Tree_Node == NULL) Rückkehr FALSCH; // leerer Baum anders Rückkehr Tree_contains_do(Tree_Node, i); // Hilfsfunktion aufrufen } // nimmt tree_node an! = Null bool Tree_contains_do(Struktur Knoten *Tree_Node, int i) { wenn (Tree_Node->Daten == i) Rückkehr Stimmt; // gefunden anders // wiederholen Rückkehr (Tree_Node->links && Tree_contains_do(Tree_Node->links, i)) || (Tree_Node->Rechts && Tree_contains_do(Tree_Node->Rechts, i)); }
Beachten Sie die Verwendung von Kurzschlussbewertung des Booleschen && (und) Operatoren, so dass der rekursive Anruf nur dann getätigt wird, wenn der Knoten gültig ist (nicht null). Beachten Sie, dass der erste Begriff im und ein Zeiger auf einen Knoten ist, der zweite Begriff ein Boolescher ist, sodass der Gesamtausdruck zu einem Booleschen bewertet wird. Dies ist eine gemeinsame Idiom bei rekursivem Kurzschluss. Dies ist zusätzlich zur Kurzschlussbewertung des Booleschen || (Oder) Operator, um das rechte Kind nur zu überprüfen, wenn das linke Kind fehlschlägt. In der Tat der gesamte Steuerfluss Von diesen Funktionen können in einer Rückgabeerklärung durch einen einzelnen booleschen Ausdruck ersetzt werden, aber die Lesbarkeit leidet ohne Nutzen der Effizienz.
Hybridalgorithmus
Rekursive Algorithmen sind aufgrund des Overheads von wiederholten Funktionsaufrufen und Rückgaben häufig ineffizient für kleine Daten. Aus diesem Grund beginnen effiziente Implementierungen rekursiver Algorithmen häufig mit dem rekursiven Algorithmus, wechseln Sie jedoch zu einem anderen Algorithmus, wenn der Eingang klein wird. Ein wichtiges Beispiel ist Zusammenführen, sortieren, was häufig durch Wechsel zum nicht rekursiven Umgang implementiert wird Sortieren durch Einfügen Wenn die Daten ausreichend klein sind, wie in der gekachelte Zusammenführungsart. Hybrid -rekursive Algorithmen können häufig weiter verfeinert werden, wie in Timsort, abgeleitet von einer Hybrid -Zusammenführungsart/-insertions -Sortierung.
Rekursion versus Iteration
Rekursion und Wiederholung sind gleichermaßen ausdrucksstark: Rekursion kann durch Iteration durch ein explizites ersetzt werden Rufen Sie Stack an, während die Iteration durch ersetzt werden kann Schwanzrekursion. Welcher Ansatz vorzuziehen ist, hängt von dem Problem und der verwendeten Sprache ab. Im Imperative ProgrammierungIteration wird bevorzugt, insbesondere für eine einfache Rekursion, da sie den Overhead von Funktionsaufrufen und den Aufruf der Stapelverwaltung vermeidet, aber die Rekursion wird im Allgemeinen für mehrere Rekursion verwendet. Dagegen in Funktionssprachen Rekursion wird bevorzugt, wobei die Schwanzrekursionsoptimierung zu wenig Overhead führt. Die Implementierung eines Algorithmus mit Iteration ist möglicherweise nicht leicht zu erreichen.
Vergleichen Sie die Vorlagen, um x zu berechnenn definiert durch xn = f (n, xN-1) von xBase:
Funktion rekursiv (n) Wenn n == Basisrückgabe xBase sonst return f (n, rekursiv (n-1)) | Funktion iterativ (n) x = xBase Für i = Basis+1 bis n x = f (i, x) return x |
Für eine imperative Sprache soll der Overhead die Funktion definieren, und für eine funktionale Sprache soll der Overhead die Akkumulatorvariable x definieren.
Zum Beispiel a Fakultät Funktion kann iterativ in implementiert werden in C durch Zuweisen einer Schleifenindexvariablen und einer Variablen der Akkumulator und nicht durch Übergabe von Argumenten und Rückgabe von Werten durch Rekursion:
ohne Vorzeichen int Fakultät(ohne Vorzeichen int n) { ohne Vorzeichen int Produkt = 1; // leeres Produkt ist 1 während (n) { Produkt *= n; --n; } Rückkehr Produkt; }
Ausdruckskraft
Die meisten Programmiersprachen Ermöglichen Sie heute die direkte Spezifikation rekursiger Funktionen und Verfahren. Wenn eine solche Funktion aufgerufen wird, des Programms Laufzeitumgebung verfolgt die verschiedenen Instanzen der Funktion (oft mit a Rufen Sie Stack an, obwohl andere Methoden angewendet werden können). Jede rekursive Funktion kann in eine iterative Funktion verwandelt werden, indem rekursive Aufrufe durch Ersetzen iterative Kontrollkonstrukte und Simulation des Anrufstacks mit einem Stapel explizit vom Programm verwaltet.[9][10]
Umgekehrt alle iterativen Funktionen und Verfahren, die von einem Computer bewertet werden können (siehe Vollständigkeit) kann in Bezug auf rekursive Funktionen ausgedrückt werden; iterative Kontrollkonstrukte wie z. während Schleifen und für Schleifen werden routinemäßig in rekursiver Form umgeschrieben in Funktionssprachen.[11][12] In der Praxis hängt diese Umschreibung jedoch davon ab Schwanzanruf Eliminierung, was kein Merkmal aller Sprachen ist. C, Java, und Python sind bemerkenswerte Mainstream -Sprachen, in denen alle Funktionsaufrufe, einschließlich Schwanzaufrufe, kann eine Stapelzuweisung verursachen, die bei der Verwendung von Schleifenkonstrukten nicht auftreten würde; In diesen Sprachen kann ein funktionierendes iteratives Programm in rekursiver Form neu geschrieben überlaufen den AnrufstapelObwohl die Schwanzaufruf -Eliminierung ein Merkmal sein kann, das nicht durch die Spezifikation einer Sprache abgedeckt wird, kann unterschiedliche Implementierungen derselben Sprache in den Rall -Eliminierungsfunktionen der Schwanz -Anrufe unterschiedlich sein.
Performance-Probleme
In Sprachen (wie z. C und Java), die iterative Looping -Konstrukte bevorzugen, es gibt normalerweise erhebliche Zeit- und Raumkosten, die mit rekursiven Programmen verbunden sind, da der Overhead für die Verwaltung des Stapels und die relative Langsamkeit der Funktionsaufrufe erforderlich ist. in Funktionssprachen, ein Funktionsaufruf (insbesondere a Schwanzanruf) ist in der Regel eine sehr schnelle Operation, und der Unterschied ist normalerweise weniger spürbar.
Als konkretes Beispiel hängt der Leistungsunterschied zwischen rekursiven und iterativen Implementierungen des obigen "faktoriellen" Beispiel Compiler Gebraucht. In Sprachen, in denen Schleifenkonstrukte bevorzugt werden Größenordnungen schneller als der rekursive. In funktionalen Sprachen kann der Gesamtzeitunterschied der beiden Implementierungen vernachlässigbar sein. Tatsächlich können die Kosten für die Multiplikation der größeren Zahlen zuerst und nicht die kleineren Zahlen (die die hier angegebene iterative Version) jederzeit überwältigen, wenn die Iteration gewählt wird.
Stapelraum
In einigen Programmiersprachen die maximale Größe des Rufen Sie Stack an ist viel weniger als der Platz in der verfügbaren Haufenund rekursive Algorithmen erfordern tendenziell mehr Stapelraum als iterative Algorithmen. Folglich legen diese Sprachen manchmal eine Grenze für die Tiefe der Rekursion, um sie zu vermeiden Stapelüberläufe; Python ist eine solche Sprache.[13] Beachten Sie die nachstehende Einschränkung bezüglich des Sonderfalles von Schwanzrekursion.
Verletzlichkeit
Da rekursive Algorithmen Stapelüberläufen ausgesetzt sein können, sind sie möglicherweise anfällig für pathologisch oder bösartig Eingang.[14] Einige Malware richten sich ausdrücklich auf den Anrufstack eines Programms und nutzen die von Natur aus rekursive Natur des Stacks.[15] Sogar ohne Malware kann ein Stapelüberlauf, der durch unbegrenzte Rekursion verursacht wird, für das Programm tödlich sein, und Ausnahmebehandlung Logik kann das entsprechende nicht verhindern Prozess vom Sein beendet.[16]
Rekursive Probleme multiplizieren
Multiplizierte rekursive Probleme sind von Natur aus rekursiv, da sie vorher verfolgen müssen. Ein Beispiel ist Baumtraversal wie in Tiefe-First-Suche; Obwohl sowohl rekursive als auch iterative Methoden verwendet werden,[17] Sie kontrastieren mit der List -Traversal- und linearen Suche in einer Liste, die eine einzeln rekursive und somit iterative Methode ist. Andere Beispiele sind Algorithmen Divide-and-Conquer-Algorithmen wie zum Beispiel Schnelle Sorteund Funktionen wie die Ackermann -Funktion. Alle diese Algorithmen können mit Hilfe eines expliziten iterativ implementiert werden StapelAber der Programmiererbemühungen, der mit der Verwaltung des Stapels und der Komplexität des resultierenden Programms verbunden ist, überwiegen wohl alle Vorteile der iterativen Lösung.
Refactoring Rekursion
Rekursive Algorithmen können durch nicht rekursive Gegenstücke ersetzt werden.[18] Eine Methode zum Ersetzen rekursiver Algorithmen besteht darin, sie mithilfe zu simulieren Heap -Speicher anstelle von Stapelspeicher.[19] Eine Alternative besteht darin, einen Ersatzalgorithmus zu entwickeln, der ausschließlich auf nicht rekursiven Methoden basiert, was eine Herausforderung sein kann.[20] Zum Beispiel rekursive Algorithmen für passende Wildcards, wie zum Beispiel Rich Salz' Wildmat Algorithmus,[21] waren einmal typisch. Nicht rekursive Algorithmen für denselben Zweck wie die Krauss Matching Wildcards Algorithmuswurden entwickelt, um die Nachteile der Rekursion zu vermeiden[22] und haben sich nur nach und nach verbessert, basierend auf Techniken wie dem Sammeln Tests und Profilerstellung Leistung.[23]
Heckrezisive Funktionen
Heckrezisive Funktionen sind Funktionen, bei denen alle rekursiven Anrufe sind Schwanzaufrufe und bauen daher keine aufgeschobenen Operationen auf. Beispielsweise ist die GCD-Funktion (unten erneut dargestellt) schwanzrekursiv. Im Gegensatz dazu ist die faktorielle Funktion (auch unten) nicht Heckrekursive; Da sein rekursiver Anruf nicht in der Schwanzposition ist, werden aufgeschobene Multiplikationsvorgänge aufgebaut, die nach Abschluss des endgültigen rekursiven Anrufs ausgeführt werden müssen. Mit einer Compiler oder Dolmetscher Das behandelt Schwanz-rezisive Anrufe als Sprünge Anstelle von Funktionsaufrufen wird eine Heckrekursive wie GCD mithilfe eines konstanten Raums ausgeführt. Somit ist das Programm im Wesentlichen iterativ und äquivalent zur Verwendung von imperativen Sprachkontrollstrukturen wie die "for" und "while".
Schwanzrekursion: | Augmenting Rekursion: |
---|---|
// Eingabe: Ganzzahlen x, y, so dass x> = y und y> = 0 int GCD(int x, int y) { wenn (y == 0) Rückkehr x; anders Rückkehr GCD(y, x % y); } | // Eingabe: n ist eine Ganzzahl, so dass n> = 0 int Tatsache(int n) { wenn (n == 0) Rückkehr 1; anders Rückkehr n * Tatsache(n - 1); } |
Die Bedeutung der Schwanzrekursion ist, dass bei einem Schwanz-rezisiven Anruf (oder einem Schwanzanruf) die Rückkehrposition des Anrufers nicht auf dem gespeichert werden muss Rufen Sie Stack an; Wenn der rekursive Anruf zurückgegeben wird, verzweigt er sich direkt auf die zuvor gespeicherte Rückkehrposition. Daher spart in Sprachen, die diese Eigenschaft von Schwanzaufrufen erkennen, sowohl Platz als auch Zeit.
Ausführungsreihenfolge
Betrachten Sie diese beiden Funktionen:
Funktion 1
Leere recursivefunktion(int num) { printf("%d\n", num); wenn (num < 4) recursivefunktion(num + 1); }
Funktion 2
Leere recursivefunktion(int num) { wenn (num < 4) recursivefunktion(num + 1); printf("%d\n", num); }
Funktion 2 ist Funktion 1 mit den ausgetauschten Zeilen.
Bei einer Funktion, die sich nur einmal aufruft, werden die Anweisungen vor dem rekursiven Aufruf einmal pro Rekursion vor dem nach dem rekursiven Anruf aufgegebenen Anweisungen ausgeführt. Letztere werden wiederholt ausgeführt, nachdem die maximale Rekursion erreicht wurde.
Beachten Sie auch, dass die bestellen der Druckanweisungen ist umgekehrt, was auf die Art und Weise zurückzuführen ist, wie die Funktionen und Aussagen auf dem gespeichert werden Rufen Sie Stack an.
Rekursive Verfahren
Fakultät
Ein klassisches Beispiel für eine rekursive Prozedur ist die Funktion zur Berechnung der Berechnung der Fakultät von a natürliche Zahl:
Pseudocode (rekursiv): |
---|
Funktion Faktorial ist: |
Die Funktion kann auch als geschrieben werden Rezidivbeziehung:
Diese Bewertung der Rezidivbeziehung zeigt die Berechnung, die bei der Bewertung des obigen Pseudocode durchgeführt wird:
Berechnung der Rezidivbeziehung für n = 4: |
---|
b4 = 4 × b3 = 4 × (3 × B2) = 4 × (3 × (2 × B)1)) = 4 × (2 × (1 × B)0))) = 4 × (3 × (2 × (1 × 1))) = 4 × (3 × (2 × 1)) = 4 × (3 × 2) = 4 × 6 = 24 |
Diese faktorielle Funktion kann auch ohne Rekursion beschrieben werden, indem die typischen Looping -Konstrukte verwendet werden, die in imperativen Programmiersprachen enthalten sind:
Pseudocode (iterativ): |
---|
Funktion Faktorial ist: |
Der obige imperative Code entspricht dieser mathematischen Definition unter Verwendung einer Akkumulatorvariable t:
Die obige Definition übersetzt unkompliziert zu Funktionale Programmiersprachen wie zum Beispiel Planen; Dies ist ein Beispiel für eine rekursive Iteration.
Größter gemeinsamer Teiler
Das Euklidischer Algorithmus, was die berechnete größter gemeinsamer Teiler von zwei Ganzzahlen können rekursiv geschrieben werden.
Funktionsdefinition:
Pseudocode (rekursiv): |
---|
Funktion GCD ist:Eingang: Ganzzahl x, Ganzzahl y so dass x > 0 und y > = 0 |
Rezidivbeziehung für den größten gemeinsamen Divisor, wo drückt die aus Rest von :
- wenn
Berechnung der Rezidivbeziehung für x = 27 und y = 9: |
---|
GCD (27, 9) = GCD (9, 27% 9) = GCD (9, 0) = 9 |
Berechnung der Rezidivbeziehung für x = 111 und y = 259: |
GCD (111, 259) = GCD (259, 111% 259) = GCD (259, 111) = GCD (111, 259% 111) = GCD (111, 37) = GCD (37, 111% 37) = GCD ((111) = GCD (GCD (37) = GCD ( 37, 0) = 37 |
Das rekursive Programm oben ist Heckrekursive; Es entspricht einem iterativen Algorithmus, und die oben gezeigte Berechnung zeigt die Bewertungsschritte, die durch eine Sprache durchgeführt werden, die Schwanzaufrufe beseitigt. Im Folgenden finden Sie eine Version desselben Algorithmus, die eine explizite Iteration unter Verwendung einer Sprache, die keine Schwanzaufrufe beseitigt. Indem er seinen Zustand vollständig in den Variablen aufrechterhält x und y Mit einem Schleifenkonstrukt vermeidet das Programm rekursive Anrufe und das Anbau des Anrufstacks.
Pseudocode (iterativ): |
---|
Funktion GCD ist: |
Der iterative Algorithmus erfordert eine vorübergehende Variable, und selbst wenn er den euklidischen Algorithmus angegeben hat, ist es schwieriger, den Prozess durch einfache Inspektion zu verstehen, obwohl die beiden Algorithmen in ihren Schritten sehr ähnlich sind.
Türme von Hanoi

Die Türme von Hanoi sind ein mathematisches Puzzle, dessen Lösung die Rekursion veranschaulicht.[24][25] Es gibt drei Stifte, die Stapel von Festplatten unterschiedlicher Durchmesser enthalten können. Eine größere Festplatte wird möglicherweise nie auf einem kleineren gestapelt. Beginnen mit n Festplatten auf einem Stift müssen nacheinander zu einem anderen Stift verlegt werden. Was ist die kleinste Anzahl von Schritten, um den Stapel zu bewegen?
Funktionsdefinition:
Rezidivbeziehung für Hanoi:
Berechnung der Rezidivbeziehung für n = 4: |
---|
Hanoi (4) = 2 × Hanoi (3) + 1 = 2 × (2 × Hanoi (2) + 1) + 1 = 2 × (2 × (2 × Hanoi (1)) + 1) + 1) + 1 = 2 × (2 × (2 × 1 + 1) + 1) + 1 = 2 × (2 × (3) + 1) + 1 = 2 × (7) + 1 = 15 |
Beispielimplementierungen:
Pseudocode (rekursiv): |
---|
Funktion Hanoi ist: |
Obwohl nicht alle rekursiven Funktionen eine explizite Lösung haben, kann der Turm der Hanoi -Sequenz auf eine explizite Formel reduziert werden.[26]
Eine explizite Formel für Türme von Hanoi: |
---|
h1 = 1 = 21 - 1 h2 = 3 = 22 - 1 h3 = 7 = 23 - 1 h4 = 15 = 24 - 1 h5 = 31 = 25 - 1 h6 = 63 = 26 - 1 h7 = 127 = 27 - 1 Im Allgemeinen: hn = 2n - 1, für alle n> = 1 |
Binäre Suche
Das binäre Suche Algorithmus ist eine Methode zur Suche nach a sortiertes Array Für ein einzelnes Element, indem Sie das Array mit jedem rekursiven Pass in zwei Hälften schneiden. Der Trick besteht darin, einen Mittelpunkt in der Nähe der Mitte des Arrays auszuwählen, die Daten an diesem Punkt mit den durchsuchten Daten zu vergleichen und dann auf eine von drei möglichen Bedingungen zu reagieren: Die Daten werden im Mittelpunkt gefunden, die Daten im Mittelpunkt sind größer als die gesuchten Daten oder die Daten im Mittelpunkt sind geringer als die gesuchten Daten.
In diesem Algorithmus wird eine Rekursion verwendet, da mit jedem Pass ein neues Array durch Schneiden des alten in die Hälfte erzeugt wird. Das binäre Suchvorgang wird dann rekursiv bezeichnet, diesmal auf dem neuen (und kleineren) Array. In der Regel wird die Größe des Arrays durch Manipulation eines Anfangs- und Endindex angepasst. Der Algorithmus weist eine logarithmische Wachstumsreihenfolge auf, da er die Problemdomäne mit jedem Pass im Wesentlichen unterteilt.
Beispiel Implementierung der binären Suche in C:
/* Rufen Sie Binary_search mit den richtigen Anfangsbedingungen an. EINGANG: Daten sind eine Reihe von Ganzzahlen, die in aufsteigender Reihenfolge sortiert sind. Tofind ist die Ganzzahl, nach der man suchen muss, Die Anzahl ist die Gesamtzahl der Elemente im Array AUSGANG: Ergebnis von Binary_Search */ int Suche(int *Daten, int finden, int zählen) { // start = 0 (Anfangsindex) // end = count - 1 (Top -Index) Rückkehr binäre Suche(Daten, finden, 0, zählen-1); } /* Binärer Suchalgorithmus. EINGANG: Daten sind eine Reihe von Ganzzahlen, die in aufsteigender Reihenfolge sortiert sind. Tofind ist die Ganzzahl, nach der man suchen muss, Start ist der Mindestarray -Index, Ende ist der maximale Array -Index AUSGANG: Position der Ganzzahl -Tofind innerhalb von Array -Daten, -1 wenn nicht gefunden */ int binäre Suche(int *Daten, int finden, int Anfang, int Ende) { // den Mittelpunkt holen. int Mitte = Anfang + (Ende - Anfang)/2; // Ganzzahl Division wenn (Anfang > Ende) // Stop -Zustand (Basisfall) Rückkehr -1; anders wenn (Daten[Mitte] == finden) // gefunden, Rückgabeindex Rückkehr Mitte; anders wenn (Daten[Mitte] > finden) // Die Daten sind größer als Tofind, suchen Sie die untere Hälfte Rückkehr binäre Suche(Daten, finden, Anfang, Mitte-1); anders // Daten sind weniger als Tofind, suchen Sie die obere Hälfte Rückkehr binäre Suche(Daten, finden, Mitte+1, Ende); }
Rekursive Datenstrukturen (Strukturrekursion)
Eine wichtige Anwendung der Rekursion in der Informatik besteht darin, dynamische Datenstrukturen wie z. Listen und Bäume. Rekursive Datenstrukturen können als Reaktion auf Laufzeitanforderungen theoretisch dynamisch zu einer theoretisch unendlichen Größe wachsen. Im Gegensatz dazu muss die Größe eines statischen Arrays zur Kompilierungszeit eingestellt werden.
"Rekursive Algorithmen sind besonders angemessen, wenn das zugrunde liegende Problem oder die zu behandelnden Daten rekursiv definiert werden."[27]
Die Beispiele in diesem Abschnitt veranschaulichen das, was als "strukturelle Rekursion" bezeichnet wird. Dieser Begriff bezieht sich auf die Tatsache, dass die rekursiven Verfahren auf Daten, die rekursiv definiert werden, auf Daten wirken.
Solange ein Programmierer die Vorlage aus einer Datendefinition ableitet, verwenden Funktionen eine strukturelle Rekursion. Das heißt, die Rekursionen im Körper einer Funktion konsumieren ein unmittelbares Stück eines bestimmten zusammengesetzten Werts.[7]
Verlinkte Listen
Im Folgenden finden Sie eine C -Definition einer verknüpften Listenknotenstruktur. Beachten Sie besonders, wie der Knoten in sich selbst definiert ist. Das "nächste" Element von Strukturknoten ist ein Zeiger auf einen anderen Strukturknoteneffektiv ein Listentyp erstellen.
Struktur Knoten { int Daten; // einige ganzzahlige Daten Struktur Knoten *nächste; // Zeiger auf einen anderen Strukturknoten };
Weil die Strukturknoten Die Datenstruktur wird rekursiv definiert. Verfahren, die darauf arbeiten, können auf natürliche Weise als rekursive Verfahren implementiert werden. Das list_print Die unten definierten Prozedur geht die Liste hinunter, bis die Liste leer ist (d. H. Der Liste Zeiger hat einen Wert von NULL). Für jeden Knoten druckt es das Datenelement (eine Ganzzahl). In der C -Implementierung bleibt die Liste unverändert von der list_print Verfahren.
Leere list_print(Struktur Knoten *aufführen) { wenn (aufführen ! = NULL) // Basisfall { printf ("%d ", aufführen->Daten); // Integer -Daten drucken, gefolgt von einem Raum list_print (aufführen->nächste); // rekursiver Anruf am nächsten Knoten } }
Binärbäume
Unten finden Sie eine einfache Definition für einen binären Baumknoten. Wie der Knoten für verknüpfte Listen ist er rekursiv in Bezug auf sich selbst definiert. Es gibt zwei selbstreferenzielle Zeiger: links (auf den linken Unterbaum zeigen) und rechts (auf den rechten Unterbaum zeigen).
Struktur Knoten { int Daten; // einige ganzzahlige Daten Struktur Knoten *links; // Zeiger auf den linken Subtree Struktur Knoten *Rechts; // Zeigen Sie auf den rechten Subtree };
Operationen am Baum können mit Rekursion implementiert werden. Beachten Sie, dass, da es zwei Selbstreferenzzeiger (links und rechts) gibt, Baumoperationen möglicherweise zwei rekursive Anrufe erfordern:
// testen Sie, ob Tree_node i; Geben Sie 1 zurück, wenn ja, 0 Wenn nicht. int Tree_contains(Struktur Knoten *Tree_Node, int i) { wenn (Tree_Node == NULL) Rückkehr 0; // Basisfall anders wenn (Tree_Node->Daten == i) Rückkehr 1; anders Rückkehr Tree_contains(Tree_Node->links, i) || Tree_contains(Tree_Node->Rechts, i); }
In den meisten beiden rekursiven Anrufen werden für einen bestimmten Anruf an getätigt Tree_contains wie oben definiert.
// In -Order Traversal: Leere Tree_print(Struktur Knoten *Tree_Node) { wenn (Tree_Node ! = NULL) { // Basisfall Tree_print(Tree_Node->links); // gehe nach links printf("%d ", Tree_Node->Daten); // Drucken Sie die Ganzzahl, gefolgt von einem Raum Tree_print(Tree_Node->Rechts); // Geh rechts } }
Das obige Beispiel zeigt eine In-Ordnung-Traversal des binären Baums. EIN Binärer Suchbaum ist ein Sonderfall des binären Baums, bei dem die Datenelemente jedes Knotens in Ordnung sind.
Dateisystem Traversal
Seit der Anzahl der Dateien in a Dateisystem variieren, Rekursion ist der einzige praktische Weg, um seinen Inhalt zu durchqueren und so aufzuzählen. Das Durchqueren eines Dateisystems ist dem von sehr ähnlich BaumtraversalDaher gelten die Konzepte hinter Baumquellen für das Durchqueren eines Dateisystems. Insbesondere wäre der folgende Code ein Beispiel für a Vorbestellung durchquert eines Dateisystems.
importieren java.io.file; Öffentlichkeit Klasse Dateisystem { Öffentlichkeit statisch Leere hauptsächlich(Saite [] Args) { Traverse(); } /** * Erhält die Wurzeln des Dateisystems * Fahrt mit dem rekursiven Dateisystem Traversal fort */ Privatgelände statisch Leere Traverse() { Datei[] fs = Datei.Listroots(); zum (int i = 0; i < fs.Länge; i++) { System.aus.println(fs[i]); wenn (fs[i].isdirectory() && fs[i].kann lesen()) { rtraverse(fs[i]); } } } /** * Überqueren Sie ein bestimmtes Verzeichnis rekursiv * * @param fd zeigt den Ausgangspunkt der Traversal an */ Privatgelände statisch Leere rtraverse(Datei FD) { Datei[] FSS = FD.Listfiles(); zum (int i = 0; i < FSS.Länge; i++) { System.aus.println(FSS[i]); wenn (FSS[i].isdirectory() && FSS[i].kann lesen()) { rtraverse(FSS[i]); } } } }
Dieser Code ist sowohl Rekursion als auch Wiederholung - Die Dateien und Verzeichnisse werden iteriert und jedes Verzeichnis wird rekursiv geöffnet.
Die "rtraverse" -Methode ist ein Beispiel für eine direkte Rekursion, während die "Traverse" -Methode eine Wrapper -Funktion ist.
Das "Basisfall" -Szenario ist, dass es in einem bestimmten Dateisystem immer eine feste Anzahl von Dateien und/oder Verzeichnissen gibt.
Zeiteffizienz rekursiver Algorithmen
Das Zeiteffizienz von rekursiven Algorithmen können in a ausgedrückt werden Rezidivbeziehung von Big O Notation. Sie können (normalerweise) dann zu einem einzigen Big-O-Begriff vereinfacht werden.
Verknüpfungsregel (Master -Theorem)
Wenn die Zeitkomplexität der Funktion in der Form ist
Dann ist das große O der Zeitkomplexität also:
- Wenn für einige Konstante , dann
- Wenn , dann
- Wenn für einige Konstante , und wenn für einige Konstante c < 1 und alles ausreichend groß n, dann
wo a repräsentiert die Anzahl der rekursiven Anrufe auf jeder Rekursionsebene, b repräsentiert durch welchen Faktor kleiner die Eingabe für die nächste Ebene der Rekursion (d. H. Die Anzahl der Teile, in die Sie das Problem teilen) und) und f(n) repräsentiert die Arbeit, dass die Funktion unabhängig von jeder Rekursion (z. B. Aufteilung, Rekombination) auf jeder Rekursionsebene leistet.
Siehe auch
- Funktionelle Programmierung
- Rechenproblem
- Hierarchische und rekursive Abfragen in SQL
- Kleene -Rosser Paradox
- Offene Rekursion
- Rekursion
- Sierpiński -Kurve
- McCarthy 91 Funktion
- μ-rekursive Funktionen
- Primitive rekursive Funktionen
- Tak (Funktion)
Anmerkungen
- ^ Graham, Ronald; Knuth, Donald; Patashnik, Oren (1990). "1: wiederkehrende Probleme". Betonmathematik. ISBN 0-201-55802-5.
- ^ Kuhail, M. A.; Negreis, J.; Seffah, A. (2021). "Lehren rekursives Denken mit Unplugged -Aktivitäten" (PDF). WTE & TE. 19: 169–175.
- ^ Epp, Susanna (1995). Diskrete Mathematik mit Anwendungen (2. Aufl.). p.427. ISBN 978-0-53494446-9.
- ^ Wirth, Niklaus (1976). Algorithmen + Datenstrukturen = Programme. Prentice-Hall. p.126. ISBN 978-0-13022418-7.
- ^ "Funktionales Programmieren | Clojure für das mutige und wahre". www.braveclojure.com. Abgerufen 2020-10-21.
- ^ Felleisen et al. 2001, Art v "Generative Rekursion
- ^ a b Fellisen, Matthias (2002). "Entwicklung interaktiver Webprogramme". In Jeuring, Johan (Hrsg.). Erweiterte funktionale Programmierung: 4. Internationale Schule (PDF). Springer. p. 108. ISBN 9783540448334.
- ^ Mongan, John; Giguère, Eric; Kindler, Noah (2013). Programmierungsinterviews enthüllt: Geheimnisse für die Landung Ihres nächsten Jobs (3. Aufl.). Wiley. p.115. ISBN 978-1-118-26136-1.
- ^ Hetland, Magnus Lie (2010), Python -Algorithmen: Mastering grundlegende Algorithmen in der Python -Sprache, Apress, p. 79, ISBN 9781430232384.
- ^ Drozdek, Adam (2012), Datenstrukturen und Algorithmen in C ++ (4. Aufl.), Cengage Learning, p. 197, ISBN 9781285415017.
- ^ Shivers, Olin. "Die Anatomie einer Schleife - eine Geschichte von Umfang und Kontrolle" (PDF). Georgia Institute of Technology. Abgerufen 2012-09-03.
- ^ Lambda das ultimative. "Die Anatomie einer Schleife". Lambda das ultimative. Abgerufen 2012-09-03.
- ^ "27.1. SYS-Systemspezifische Parameter und Funktionen-Python v2.7.3 Dokumentation". Docs.python.org. Abgerufen 2012-09-03.
- ^ Krauss, Kirk J. (2014). "Matching Wildcards: Eine empirische Möglichkeit, einen Algorithmus zu zähmen". Dr. Dobbs Journal.
- ^ Mueller, Oliver (2012). "Anatomie eines Stapelangriffs und wie GCC sie verhindert". Dr. Dobbs Journal.
- ^ "Stackoverflowexception -Klasse". .NET Framework -Klassenbibliothek. Microsoft Developer Network. 2018.
- ^ "Tiefe erste Suche (DFS): iterative und rekursive Implementierung". Techie Freude. 2018.
- ^ Mitrovic, Ivan. "Ersetzen Sie die Rekursion durch Iteration". Gedankenwerke.
- ^ La, Woong Gyu (2015). "So ersetzen Sie rekursive Funktionen mit Stack und während des Schleifens, um den Stack-Overflow zu vermeiden.". CodeProject.
- ^ Moertel, Tom (2013). "Tricks des Handels: Rekursion zur Iteration, Teil 2: Eliminierung der Rekursion mit dem geheimen Feature-Trick der Zeitreise".
- ^ Salz, Rich (1991). "Wildmat.c". GitHub.
- ^ Krauss, Kirk J. (2008). "Passende Wildcards: Ein Algorithmus". Dr. Dobbs Journal.
- ^ Krauss, Kirk J. (2018). "Matching Wildcards: Ein verbesserter Algorithmus für Big Data". Für die Leistung entwickeln.
- ^ Graham, Knuth & Patashnik 1990, §1.1: Der Turm von Hanoi
- ^ EPP 1995, S. 427–430: Der Turm von Hanoi
- ^ EPP 1995, S. 447–448: Eine explizite Formel für den Turm der Hanoi -Sequenz
- ^ Wirth 1976, p. 127
Verweise
- Barron, David William (1968) [1967]. Geschrieben in Cambridge, Großbritannien. Gill, Stanley (ed.). Rekursive Techniken in der Programmierung. MacDonald Computermonographien (1 Ed.). London, Vereinigtes Königreich: MacDonald & Co. (Publishers) Ltd. Sbn 356-02201-3. (viii+64 Seiten)
- Fellisen, Matthias; Findler, Robert B.; Flatt, Matthew; Krishnamurthi, Shriram (2001). Gestaltung von Programmen: Eine Einführung in das Computer und Programmieren. MIT Press. ISBN 0262062186.
- Rubio-Sanchez, Manuel (2017). Einführung in die rekursive Programmierung. CRC Press. ISBN 978-1-351-64717-5.
- Pevac, Irena (2016). Übungsrekursion in Java. CreateSpace unabhängig. ISBN 978-1-5327-1227-2.
- Roberts, Eric (2005). Rekursiv mit Java denken. Wiley. ISBN 978-0-47170146-0.
- Rohl, Jeffrey S. (1984). Rekursion über Pascal. Cambridge University Press. ISBN 978-0-521-26934-6.
- Helman, Paul; Veroff, Robert. Wände und Spiegel.
- Abelson, Harold; Sussman, Gerald Jay; Sussman, Julie (1996). Struktur und Interpretation von Computerprogrammen (2. Aufl.). MIT Press. ISBN 0-262-51087-1.
- Dijkstra, Edsger W. (1960). "Rekursive Programmierung". Numerische Mathematik. 2 (1): 312–318. doi:10.1007/bf01386232. S2CID 127891023.