Rekursion

Eine visuelle Form der Rekursion, die als die bekannt ist Drosteeffekt. Die Frau in diesem Bild enthält ein Objekt, das ein kleineres Bild von ihr enthält, das ein identisches Objekt hält, das wiederum ein kleineres Bild von sich enthält, das ein identisches Objekt hält, und so weiter. 1904 Droste Kakao Zinn, entworfen von Jan Musset

Rekursion (Adjektiv: rekursiv) tritt auf, wenn etwas in Bezug auf sich selbst oder von ihrem Typ definiert wird. Rekursion wird in einer Vielzahl von Disziplinen verwendet, die von Linguistik zu Logik. Die häufigste Anwendung von Rekursion ist in Mathematik und Informatik, wo ein Funktion definiert wird in seiner eigenen Definition angewendet. Während dies offenbar eine unendliche Anzahl von Instanzen (Funktionswerte) definiert, wird dies häufig so erfolgen, dass keine unendliche Schleife oder unendliche Kette von Referenzen ("Crock -Rekursion") auftreten kann.

Formale Definitionen

Ouroboros, ein altes Symbol, das eine Schlange oder einen Drachen zeigt, der seinen eigenen Schwanz frisst.

In Mathematik und Informatik zeigt eine Klasse von Objekten oder Methoden ein rekursives Verhalten, wenn sie durch zwei Eigenschaften definiert werden können:

• Eine einfache Basisfall (oder Fälle) - Ein Kündigungsszenario, in dem keine Rekursion verwendet wird, um eine Antwort zu erzeugen
• A rekursiver Schritt - Eine Reihe von Regeln, die alle aufeinanderfolgenden Fälle auf den Basisfall reduzieren.

Zum Beispiel ist das Folgende eine rekursive Definition einer Person einer Person Vorfahr. Der Vorfahr ist entweder:

• Eltern (Eltern (Basisfall), oder
• Vorfahr des Elternteils (rekursiver Schritt).

Das Fibonacci-Folge ist ein weiteres klassisches Beispiel für Rekursion:

Fib (0) = 0 als Basisfall 1,

Fib (1) = 1 als Basisfall 2,

Für alle Ganzzahlen n > 1, Flunkerei(n) = Fib (n - 1) + fib (n - 2).

Viele mathematische Axiome basieren auf rekursiven Regeln. Zum Beispiel die formale Definition der natürliche Zahlen bis zum Peano -Axiome kann beschrieben werden als: "Null ist eine natürliche Zahl, und jede natürliche Zahl hat einen Nachfolger, der auch eine natürliche Zahl ist."^[1] Nach diesem Basisfall und rekursiven Regel kann man den Satz aller natürlichen Zahlen erzeugen.

Andere rekursiv definierte mathematische Objekte umfassen Faktorien, Funktionen (z.B., Wiederholungsbeziehungen), Sets (z.B., Cantor -Ternär -Set), und Fraktale.

Es gibt verschiedene freche Definitionen der Rekursion; sehen rekursiver Humor.

Informelle Definition

Kürzlich aktualisiert Sauerteig, durchblasen Fermentation: Das Rezept fordert einige Sauerteig, die vom letzten Mal das gleiche Rezept gemacht wurde.

Rekursion ist der Prozess, den ein Verfahren durchläuft, wenn einer der Schritte des Verfahrens das Aufrufen des Verfahrens selbst besteht. Ein Verfahren, das eine Rekursion durchläuft, soll "rekursiv" sein.^[2]

Um die Rekursion zu verstehen, muss man die Unterscheidung zwischen einem Verfahren und dem Ausführen eines Verfahrens erkennen. Ein Verfahren ist eine Reihe von Schritten, die auf einer Reihe von Regeln basieren, während das Ausführen eines Prozedur die Tatsache der Regeln und die Ausführung der Schritte umfasst.

Die Rekursion bezieht sich auf eine Referenz innerhalb der Spezifikation eines Verfahrens auf die Ausführung eines anderen Verfahrens.

Wenn ein Verfahren als solches definiert wird, schafft dies sofort die Möglichkeit einer endlosen Schleife. Rekursion kann nur in einer Definition ordnungsgemäß verwendet werden, wenn der fragliche Schritt in bestimmten Fällen übersprungen wird, damit das Verfahren abgeschlossen werden kann. Rekursion ist in drei Formen erhältlich: Direkte, indirekt, und kreisförmig. Direkte Rekursion ist, wenn eine Funktion (a) sich selbst aufruft (A Referenzen a); Die indirekte Rekursion tritt auf, wenn eine Funktion (a) (b), die Funktion (b) Funktion (c), Funktion (c) aufgerufen (d) usw., bis eine der Funktionen in der Kette eine frühere aufruft. Die kreisförmige Rekursion tritt auf, wenn die Funktion (a) und die Funktion (b) sich gegenseitig aufrufen. Wenn eine unendliche Schleife in direkter, indirekter oder kreisförmiger Rekursion auftritt, wird bezeichnet, dass es sich um den Zustand der "Crock -Rekursion" handelt. Grundsätzlich gibt es zwei Möglichkeiten, um die Crock -Rekursion zu verhindern, entweder die Anzahl der Zeiten zu begrenzen, die eine Funktion selbst verweisen kann, oder eine absolute Grenze für die Funktionstiefe der Funktionsabrufe legen, z. Wenn es eine Tiefengrenze von 50 gibt, wird ein Verfahren, wenn ein Verfahren einen anderen Anruf aufruft, ein Zähler erhöht. Wenn es ausgeht, wird dieser Zähler verringert. Sobald der Zähler die Grenze erreicht hat (in diesem Fall 50), sind keine weiteren Verfahrensanrufe zulässig; Wenn versucht wird, eine 51. Funktion aufzurufen, wird die Operation beendet. Die Verwendung einer Rekursionsgrenze verhindert nur eine Crock -Rekursion; Durch das Platzieren einer Anrufbeschränkung können Sie zusätzlich zum Anhalten von Crock -Rekursion die Nebenwirkung haben, die Ausführung legitimer komplexer Verfahren zu verhindern, die tief verschachtelt, aber nicht rekursiv sind.

Aber selbst wenn es ordnungsgemäß definiert ist, ist ein rekursives Verfahren für die Menschen nicht einfach, da die Neue von der alten, teilweise ausgeführten Berufung des Verfahrens unterschieden werden muss. Dies erfordert eine Verwaltung, wie weit verschiedene gleichzeitige Fälle der Verfahren fortgeschritten sind. Aus diesem Grund sind rekursive Definitionen in alltäglichen Situationen sehr selten.

In der Sprache

Linguist Noam Chomskyunter anderem hat argumentiert, dass das Fehlen einer Obergrenze an der Anzahl der grammatikalischen Sätze in einer Sprache und das Fehlen einer Obergrenze der grammatikalischen Satzlänge (jenseits der praktischen Einschränkungen wie der Zeit, die für das Äußere verfügbar ist), kann als Folge der Rekursion in der natürlichen Sprache erklärt werden.^[3][4]

Dies kann anhand einer rekursiven Definition einer syntaktischen Kategorie wie einem Satz verstanden werden. Ein Satz kann eine Struktur haben, in der das, was dem Verb folgt, ein weiterer Satz ist: Dorothy denkt, Hexen sind gefährlich, in dem der Satz Hexen sind gefährlich tritt im größeren vor. Ein Satz kann also rekursiv (sehr grob) als etwas mit einer Struktur definiert werden, die eine Substantivphrase, ein Verb und optional einen anderen Satz enthält. Dies ist wirklich nur ein besonderer Fall der mathematischen Definition von Rekursion.

Dies bietet eine Möglichkeit, die Kreativität der Sprache zu verstehen - die unbegrenzte Anzahl grammatikalischer Sätze -, weil sie sofort voraussagen, dass Sätze von willkürlicher Länge sein können: Dorothy glaubt, dass Toto vermutet, dass Tin Man das gesagt hat .... Abgesehen von Sätzen gibt es viele Strukturen, die rekursiv definiert werden können, und daher viele Möglichkeiten, wie ein Satz Instanzen einer Kategorie in eine andere einbetten kann.^[5] Im Laufe der Jahre haben sich Sprachen im Allgemeinen für diese Art von Analyse erwiesen.

In jüngster Zeit wurde jedoch die allgemein anerkannte Idee, dass eine Rekursion ein wesentliches Eigentum der menschlichen Sprache ist Daniel Everett Aufgrund seiner Behauptungen über die Pirahã -Sprache. Andrew Nevins, David Pesetsky und Cilene Rodrigues sind unter vielen, die dagegen argumentiert haben.^[6] Literarisch Selbstreferenz kann in jedem Fall als unterschiedlich von mathematischer oder logischer Rekursion unterschiedlich sein.^[7]

Rekursion spielt nicht nur eine entscheidende Rolle bei Syntax, sondern auch in Natürliche Sprachsemantik. Das Wort undkann beispielsweise als eine Funktion ausgelegt werden, die für Satzbedeutungen angewendet werden kann, um neue Sätze zu erstellen, und ebenfalls für Nomen -Phrasenbedeutungen, Verb -Phrasenbedeutungen und andere. Es kann auch auf intransitive Verben, transitive Verben oder ditransitive Verben gelten. Um eine einzelne Bezeichnung dafür bereitzustellen, die angemessen flexibel ist, und wird normalerweise definiert, damit diese unterschiedlichen Arten von Bedeutungen als Argumente erfolgen können. Dies kann durch Definieren eines einfachen Falls erfolgen, in dem es Sätze kombiniert und dann die anderen Fälle rekursiv in Bezug auf die einfache definiert.^[8]

A rekursive Grammatik ist eine formale Grammatik, die rekursiv enthält Produktionsregeln.^[9]

Rekursiver Humor

Eine rekursive Wikipedia Seite

Rekursion wird manchmal humorvoll in Informatik, Programmierung, Philosophie oder Mathematik -Lehrbüchern verwendet, indem er im Allgemeinen a Kreisendefinition oder Selbstreferenz, in dem der mutmaßliche rekursive Schritt nicht näher an einen Basisfall kommt, sondern stattdessen zu einem führt unendlich zurückgeblieben. Es ist nicht ungewöhnlich, dass solche Bücher einen Witzeintrag in ihr Glossar in den Sicht stellen:

Rekursion, Siehe Rekursion.^[10]

Eine Variation finden Sie auf Seite 269 in der Index von einigen Ausgaben von Brian Kernighan und Dennis Ritchie's Buch Die C -Programmiersprache; Der Indexeintrag verweist rekursiv selbst ("Rekursion 86, 139, 141, 182, 202, 269"). Frühe Versionen dieses Witzes finden Sie in Reden wir Lisp Sprechen Von Laurent Siklóssy (veröffentlicht von Prentice Hall PTR am 1. Dezember 1975, mit einem Urheberrecht von 1976) und in Software-Tools Von Kernighan und Plauger (veröffentlicht von Addison-Wesley Professional am 11. Januar 1976). Der Witz erscheint auch in Die UNIX -Programmierumgebung von Kernighan und Pike. Es erschien nicht in der ersten Ausgabe von Die C -Programmiersprache. Der Witz ist Teil der Funktionelle Programmierung Folklore und war bereits vor der Veröffentlichung der oben genannten Bücher in der funktionalen Programmiergemeinschaft weit verbreitet.

Ein weiterer Witz ist, dass "Sie Rekursion verstehen müssen, Sie müssen die Rekursion verstehen".^[10] In der englischsprachigen Version der Google-Web-Suchmaschine, wenn eine Suche nach "Rekursion" durchgeführt wird, schlägt die Website vor: "Meinten Sie: Rekursion. "^[11] Eine alternative Form ist die folgende, von Andrew Plotkin: "Wenn Sie bereits wissen, was Rekursion ist, denken Sie an die Antwort. Ansonsten finden Sie jemanden, der näher steht Douglas Hofstadter als du bist; Dann fragen Sie ihn oder sie, was Rekursion ist. "

Rekursive Akronyme sind andere Beispiele für rekursives Humor. PhpZum Beispiel steht für "PHP Hypertext Preprozessor", WEIN steht für "Wein ist kein Emulator" GNU steht für "Gnu's nicht Unix" und Sparql bezeichnet das "Sparql -Protokoll und die RDF -Abfragesprache".

In Mathematik

Das Sierpinski -Dreieck- Eine begrenzte Überholung von Dreiecken, die ein fraktales bilden

Rekursiv definierte Sätze

Beispiel: Die natürlichen Zahlen

Das kanonische Beispiel eines rekursiv definierten Satzes wird von der gegeben natürliche Zahlen:

0 ist in ${\ displaystyle \ mathbb {n}}$

wenn n ist in ${\ displaystyle \ mathbb {n}}$, dann n + 1 ist in ${\ displaystyle \ mathbb {n}}$

Der Satz natürlicher Zahlen ist der kleinste Satz, der die beiden vorherigen Eigenschaften erfüllt.

In der mathematischen Logik die Peano -Axiome (oder Peano Postulate oder Dedekind -Peano -Axiome) sind Axiome für die natürlichen Zahlen, die im 19. Jahrhundert vom deutschen Mathematiker präsentiert wurden Richard Dedekind und vom italienischen Mathematiker Giuseppe Peano. Die Peano -Axiome definieren die natürlichen Zahlen, die sich auf eine rekursive Nachfolgerfunktion sowie Addition und Multiplikation als rekursive Funktionen beziehen.

Beispiel: Beweisverfahren

Ein weiteres interessantes Beispiel ist das Satz aller "nachweisbaren" Vorschläge in einem Axiomatisches System das sind in Bezug auf a definiert Beweisverfahren die induktiv (oder rekursiv) wie folgt definiert wird:

• Wenn ein Satz ein Axiom ist, ist es ein nachweisbarer Satz.
• Wenn ein Vorschlag aus echten erreichbaren Aussagen mittels Inferenzregeln abgeleitet werden kann, ist es ein nachweisbarer Satz.
• Die Reihe von nachweisbaren Vorschlägen ist die kleinste Aussage, die diese Bedingungen erfüllen.

Finite Unterteilung Regeln

Finite-Subdivision-Regeln sind eine geometrische Rekursionsform, mit der fraktalähnliche Bilder erzeugt werden können. Eine Unterteilung Regel beginnt mit einer Sammlung von Polygonen, die endlich viele Etiketten bezeichneten, und dann wird jedes Polygon in kleinere markierte Polygone auf eine Weise unterteilt, die nur von den Etiketten des ursprünglichen Polygons abhängt. Dieser Prozess kann iteriert werden. Die Standardtechnik der mittleren Drittel zum Erstellen der Cantor -Set ist eine Unterteilungsregel, wie es ist ist Barycentric Subdivision.

Funktionsrekursion

A Funktion kann rekursiv in Bezug auf sich selbst definiert werden. Ein vertrautes Beispiel ist das Fibonacci -Nummer Reihenfolge: F(n) = F(n - 1) + F(n - 2). Damit eine solche Definition nützlich ist, muss sie auf nicht rekursiv definierte Werte reduzierbar sein: in diesem Fall F(0) = 0 und F(1) = 1.

Eine berühmte rekursive Funktion ist die Ackermann -Funktion, was im Gegensatz zur Fibonacci -Sequenz nicht ohne Rekursion exprimiert werden kann.

Beweise mit rekursiven Definitionen

Anwendung der Standardtechnik von Beweis nach Fällen rekursiv definierte Sätze oder Funktionen wie in den vorhergehenden Abschnitten ergibt strukturelle Induktion - Eine starke Verallgemeinerung von mathematische Induktion weithin verwendet, um Beweise in abzuleiten Mathematische Logik und Informatik.

Rekursive Optimierung

Dynamische Programmierung ist ein Ansatz zu Optimierung Dies stellt ein Multiperioden- oder Mehrfach -Optimierungsproblem in rekursiver Form zurück. Das Schlüsselergebnis bei dynamischer Programmierung ist die Bellman -Gleichung, der den Wert des Optimierungsproblems zu einem früheren Zeitpunkt (oder früheren Schritt) in Bezug auf seinen Wert zu einem späteren Zeitpunkt (oder später) schreibt.

Der Rekursionstheorem

Im MengenlehreDies ist ein Satz, der garantiert, dass rekursiv definierte Funktionen existieren. Ein Satz gegeben X, ein Element a von X und eine Funktion f: X → XDas Theorem gibt an, dass es eine einzigartige Funktion gibt ${\ displayStyle f: \ mathbb {n} \ bis x}$ (wo ${\ displaystyle \ mathbb {n}}$ bezeichnet die Menge der natürlichen Zahlen, einschließlich Null), so dass

${\ displayStyle f (0) = a}$

${\ displayStyle f (n+1) = f (f (n))}$

für jede natürliche Zahl n.

Beweis der Einzigartigkeit

Nehmen Sie zwei Funktionen ${\ displayStyle f: \ mathbb {n} \ bis x}$ und ${\ displaystyle g: \ mathbb {n} \ bis x}$ so dass:

${\ displayStyle f (0) = a}$

${\ displayStyle g (0) = a}$

${\ displayStyle f (n+1) = f (f (n))}$

${\ displayStyle g (n+1) = f (g (n))}$

wo a ist ein Element von X.

Es kann durch Beweis mathematische Induktion das F(n) = G(n) Für alle natürlichen Zahlenn:

Basisfall: F(0) = a = G(0) Also gilt die Gleichheit für n = 0.

Induktiver Schritt: Vermuten F(k) = G(k) für einige ${\ displayStyle k \ in \ mathbb {n}}$. Dann F(k + 1) = f(F(k)) = f(G(k)) = G(k + 1).

Somit F(k) = G(k) impliziert F(k + 1) = G(k + 1).

Durch Induktion, F(n) = G(n) für alle ${\ displayStyle n \ in \ mathbb {n}}$.

In Informatik

Eine häufige Vermittlungsmethode besteht darin, ein Problem in Unterprobleme desselben Typs zu unterteilen. Als ein Computerprogrammierung Technik, das heißt teilen und erobern und ist der Schlüssel zum Design vieler wichtiger Algorithmen. Divide und Eroberer dienen als Top-Down-Ansatz für die Problemlösung, bei denen Probleme durch die Lösung immer kleinerer Instanzen gelöst werden. Ein gegenteiliger Ansatz ist Dynamische Programmierung. Dieser Ansatz dient als Bottom-up-Ansatz, bei dem Probleme gelöst werden, indem immer größere Instanzen gelöst werden, bis die gewünschte Größe erreicht ist.

Ein klassisches Beispiel für eine Rekursion ist die Definition der Fakultät Funktion, hier in C Code:

ohne Vorzeichen int Fakultät(ohne Vorzeichen int n) {   wenn (n == 0) {   Rückkehr 1;   } anders {   Rückkehr n * Fakultät(n - 1);   } } 

Die Funktion ruft sich rekursiv auf einer kleineren Version des Eingangs auf (n - 1) und multipliziert das Ergebnis des rekursiven Aufrufs von nbis zum Erreichen des Basisfallanalog zur mathematischen Definition von Faktor.

Die Rekursion der Computerprogrammierung wird beispielhaft veranschaulicht, wenn eine Funktion in Bezug auf einfachere, oft kleinere Versionen von sich selbst definiert wird. Die Lösung für das Problem wird dann durch Kombination der Lösungen entwickelt, die aus den einfacheren Versionen des Problems erhalten wurden. Eine Beispielanwendung von Rekursion ist in Parser Für Programmiersprachen. Der große Vorteil der Rekursion besteht darin, dass ein unendlicher Satz möglicher Sätze, Designs oder anderer Daten von einem endlichen Computerprogramm definiert, analysiert oder erzeugt werden kann.

Wiederholungsbeziehungen sind Gleichungen, die eine oder mehrere Sequenzen rekursiv definieren. Einige spezifische Arten von Rezidivbeziehungen können "gelöst" werden, um eine nicht rekursive Definition zu erhalten (z. B. a Expression geschlossene Form).

Die Verwendung von Rekursion in einem Algorithmus hat sowohl Vor- als auch Nachteile. Der Hauptvorteil ist normalerweise die Einfachheit der Anweisungen. Der Hauptnachteil ist, dass die Speicherverwendung rekursiver Algorithmen sehr schnell wachsen kann und sie für größere Fälle unpraktisch macht.

In Biologie

Formen, die anscheinend durch rekursive Prozesse geschaffen worden zu sein scheinen, treten manchmal in Pflanzen und Tieren auf, beispielsweise in verzweigten Strukturen, in denen ein großer Teil in zwei oder ähnliche kleinere Teile verzweigt. Ein Beispiel ist Romanesco Broccoli.^[12]

In Kunst

Rekursive Puppen: der ursprüngliche Satz von Matryoshka -Puppen durch Zvyozdochkin und Malyutin, 1892

Vorderseite von Giotto's Stefaneschi Triptychon, 1320, enthält rekursiv ein Bild von sich selbst (gehalten von der knienden Figur im zentralen Panel).

Die russische Puppe oder Matryoshka -Puppe ist ein physisches künstlerisches Beispiel für das rekursive Konzept.^[13]

Rekursion wurde seitdem in Gemälden verwendet Giotto's Stefaneschi Triptychon, 1320 hergestellt. Sein zentrales Panel enthält die kniende Figur von Kardinal Stefanesschi, die das Triptychon selbst als Angebot hochhält.^[14][15] Diese Praxis ist allgemein bekannt als die Drosteeffektein Beispiel der Mise en Abyme Technik.

M. C. Escher's Druckgalerie (1956) ist ein Druck, der eine verzerrte Stadt mit einer Galerie zeigt, die eine Galerie enthält, die rekursiv enthält das Bild und so Ad infinitum.^[16]

Siehe auch

Verweise

Literaturverzeichnis

Externe Links

• Rekursion - Tutorial von Alan Gauld
• Zip -Dateien bis zum Ende
• Nevins, Andrew und David Pesetsky und Cilene Rodrigues. Beweise und Argumentation: Eine Antwort an Everett (2009). Sprache 85.3: 671-681 (2009)