Recursion ist der Prozess von sich wiederholenden Sachen auf eine selbstähnliche Weise. Zum Beispiel, wenn die Oberflächen von zwei Spiegeln mit einander die verschachtelten Images genau parallel sind, die vorkommen, sind eine Form von unendlichem recursion. Der Begriff hat eine Vielfalt von Bedeutungen, die zu einer Vielfalt von Disziplinen im Intervall von der Linguistik zur Logik spezifisch sind. Die allgemeinste Anwendung von recursion ist in der Mathematik und Informatik, in der es sich auf eine Methode bezieht, Funktionen zu definieren, in denen die Funktion, die wird definiert, innerhalb seiner eigenen Definition angewandt wird. Spezifisch definiert das eine unendliche Zahl von Beispielen (Funktionswerte) mit einem begrenzten Ausdruck, der sich für einige Beispiele auf andere Beispiele beziehen kann, aber auf solche Art und Weise dass keine Schleife oder unendliche Kette von Verweisungen vorkommen können. Der Begriff wird auch mehr allgemein gebraucht, um einen Prozess zu beschreiben, Gegenstände auf eine selbstähnliche Weise zu wiederholen.

Formelle Definitionen von recursion

In der Mathematik und Informatik stellt eine Klasse von Gegenständen oder Methoden rekursives Verhalten aus, wenn sie durch zwei Eigenschaften definiert werden können:

1. Ein einfacher Grundfall (oder Fälle), und
2. Eine Reihe von Regeln, die alle anderen Fälle zum Grundfall reduzieren.

Zum Beispiel ist der folgende eine rekursive Definition Vorfahren einer Person:

• Jemandes Eltern sind jemandes Vorfahren (Grundfall).
• Die Eltern von jemandes Vorfahren sind auch jemandes Vorfahren (recursion Schritt).

Die Fibonacci Folge ist ein klassisches Beispiel von recursion:

• Flunkerei (0) ist 0 [Grundfall]
• Flunkerei (1) ist 1 [Grundfall]
• Für alle ganzen Zahlen n> 1: Flunkerei (n) ist (Flunkerei (n-1) + Flunkerei (n-2)) [rekursive Definition]

Viele mathematische Axiome basieren laut rekursiver Regeln. Zum Beispiel folgt die formelle Definition der natürlichen Zahlen in der Mengenlehre: 1 ist eine natürliche Zahl, und jede natürliche Zahl hat einen Nachfolger, der auch eine natürliche Zahl ist. Durch diesen Grundfall und rekursive Regel kann man den Satz aller natürlichen Zahlen erzeugen

Eine humorvollere Illustration geht: "Um recursion zu verstehen, müssen Sie zuerst recursion verstehen." Oder vielleicht genauer ist das folgende von Andrew Plotkin: "Wenn Sie bereits wissen, wie recursion ist, erinnern Sie sich gerade an die Antwort. Finden Sie sonst jemanden, der an Douglas Hofstadter näheres Stehen ist, als Sie sind; dann fragen Sie ihn oder sie, wie recursion ist."

Rekursiv definierte mathematische Gegenstände schließen Funktionen, Sätze, und besonders fractals ein.

Recursion auf der Sprache

Linguist Noam Chomsky theoretisiert, dass die unbegrenzte Erweiterung jeder natürlichen Sprache das mögliche Verwenden des rekursiven Geräts ist, Klauseln innerhalb von Sätzen einzubetten. Zum Beispiel haben zwei einfache Sätze — "Dorothy die Schlechte Hexe des Westens im Munchkin-Land getroffen", und "die Schwester der Schlechten Hexe wurde im Munchkin-Land getötet" — kann in einem dritten Satz eingebettet werden, "Dorothy hat die Schlechte Hexe mit einem Eimer von Wasser," liquidiert, einen rekursiven Satz zu erhalten: "Dorothy, die die Schlechte Hexe des Westens im Munchkin-Land getroffen hat, wo ihre Schwester getötet wurde, hat sie mit einem Eimer von Wasser liquidiert."

Die Idee, dass recursion ein wesentliches Eigentum der menschlichen Sprache ist (weil schlägt Chomsky vor), wird vom Linguisten Daniel Everett in seiner Arbeit Kulturelle Einschränkungen auf die Grammatik und das Erkennen in Pirahã herausgefordert: Ein Anderer Blick auf die Designeigenschaften der Menschlichen Sprache, auf der er Hypothese aufstellt, dass kulturelle Faktoren recursion unnötig in der Entwicklung der Sprache von Pirahã gemacht haben. Dieses Konzept, das die Idee von Chomsky herausfordert, dass recursion der einzige Charakterzug ist, der Menschen und Tierkommunikation unterscheidet, ist zurzeit unter der Debatte.

Andrew Nevins, David Pesetsky und Cilene Rodrigues stellen eine Debatte gegen diesen Vorschlag zur Verfügung. Indirekter Beweis, dass die Ideen von Everett falsch sind, kommt aus Arbeiten in neurolinguistics, wo es scheint, dass alle Menschen mit selben neurobiological Strukturen ausgestattet sind, um sich mit allen und nur rekursiven Sprachen zu behelfen. Für eine Rezension, sieh Kaan u. a. (2002)

Recursion in der Linguistik ermöglicht 'getrennte Unendlichkeit' durch das Einbetten von Ausdrücken innerhalb von Ausdrücken desselben Typs in einer hierarchischen Struktur. Ohne recursion hat Sprache 'getrennte Unendlichkeit' nicht und kann Sätze in die Unendlichkeit (mit einer 'russischen Matrjoschka' Wirkung) nicht einbetten. Everett wetteifert diese Sprache muss getrennte Unendlichkeit haben und behauptet, dass die Sprache von Pirahã - den er fordert, fehlt, ist recursion - tatsächlich begrenzt. Er vergleicht es mit dem begrenzten Spiel des Schachs, das eine begrenzte Zahl von Bewegungen hat, aber dennoch mit neuartigen Bewegungen sehr produktiv ist, die überall in der Geschichte entdecken werden.

Recursion unmissverständlich

Recursion ist der Prozess, den ein Verfahren durchgeht, wenn einer der Schritte des Verfahrens das Hervorrufen des Verfahrens selbst einschließt. Wie man sagt, ist ein Verfahren, das recursion durchgeht, 'rekursiv'.

Um recursion zu verstehen, muss man die Unterscheidung zwischen einem Verfahren und dem Laufen eines Verfahrens anerkennen. Ein Verfahren ist eine Reihe von Schritten, die gestützt auf einer Reihe von Regeln genommen werden sollen. Das Laufen eines Verfahrens ist wirklich im Anschluss an die Regeln und das Durchführen der Schritte verbunden. Eine Analogie könnte sein, dass ein Verfahren einem Kochbuch ähnlich ist, in dem es die möglichen Schritte sind, während das Laufen eines Verfahrens wirklich die Mahlzeit vorbereitet.

Recursion ist mit, aber nicht dasselbe als, eine Verweisung innerhalb der Spezifizierung eines Verfahrens zur Ausführung eines anderen Verfahrens verbunden. Zum Beispiel könnte sich ein Rezept auf das Kochen von Gemüsepflanzen beziehen, der ein anderes Verfahren ist, das der Reihe nach Heizungswasser und so weiter verlangt. Jedoch ist ein rekursives Verfahren darin speziell (mindestens) ein seiner Schritte verlangen nach einem neuen Beispiel selben Verfahrens wie ein Sauerteig-Rezept, das nach einem Geld verlassen vom letzten Mal verlangt, als dasselbe Rezept gemacht wurde. Das schafft natürlich sofort die Möglichkeit einer endlosen Schleife; recursion kann nur in einer Definition richtig verwendet werden, wenn der fragliche Schritt in bestimmten Fällen ausgelassen wird, so dass das Verfahren wie ein Sauerteig-Rezept vollenden kann, das Ihnen auch erzählt, wie man ein Starter-Geld bekommt, im Falle dass Sie es vorher nie gemacht haben. Selbst wenn richtig definiert ein rekursives Verfahren für Menschen nicht leicht ist zu leisten, weil es das Unterscheiden des neuen vom alten (teilweise durchgeführt) Beschwörung des Verfahrens verlangt; das verlangt eine Regierung dessen, wie weit verschiedene gleichzeitige Beispiele der Verfahren fortgeschritten sind. Aus diesem Grund sind rekursive Definitionen in täglichen Situationen sehr selten. Ein Beispiel konnte das folgende Verfahren sein, um einen Weg durch einen Irrgarten zu finden. Gehen Sie vorwärts bis zum Erreichen entweder ein Ausgang oder ein sich verzweigender Punkt weiter (ein toter Punkt wird als ein sich verzweigender Punkt mit 0 Zweigen betrachtet). Wenn der erreichte Punkt ein Ausgang, begrenzt ist. Versuchen Sie sonst jeden Zweig der Reihe nach mit dem Verfahren rekursiv; wenn jede Probe durch das Erreichen von nur toten Punkten scheitert, kehren Sie auf dem Pfad zurück, der zu diesem sich verzweigenden Punkt und Berichtsmisserfolg geführt hat. Ob das wirklich ein endendes Verfahren definiert, hängt von der Natur des Irrgartens ab: Es muss Schleifen nicht erlauben. Jedenfalls verlangt Durchführung des Verfahrens sorgfältig Aufnahme von allen zurzeit erforschte sich verzweigende Punkte, und welcher von ihren Zweigen bereits erschöpfend versucht worden ist.

Rekursiver Humor

Recursion wird manchmal humorvoll in Informatik, Programmierung, Philosophie oder Mathematik-Lehrbüchern verwendet. Es ist für solche Bücher ziemlich üblich, einen Witz-Zugang in ihr Wörterverzeichnis entlang den Linien einzuschließen:

:Recursion, sieh Recursion.

Eine Schwankung wird im Index auf der Seite 269 von einigen Ausgaben von Kernighan und dem Buch von Ritchie "Die C Programmiersprache" gefunden; so der Index-Zugang rekursiv Verweisungen selbst ("recursion 86, 139, 141, 182, 202, 269"). Die frühste Version dieses Witzes war in "Softwarewerkzeugen" durch Kernighan und Plauger, und erscheint auch "im UNIX Programmierung der Umgebung" durch Kernighan und Hecht. Es ist in der Erstausgabe Der C Programmiersprache nicht erschienen.

Ein anderer Witz ist, dass, "Um recursion zu verstehen, Sie recursion verstehen müssen." In der englischen Sprachversion des Websuchmotors von Google, wenn eine Suche "recursion" gemacht wird, deutet die Seite an "Hat getan Sie haben vor: recursion."

Rekursive Akronyme können auch Beispiele des rekursiven Humors sein. PHP tritt zum Beispiel "für PHP Hypertext-Vorverarbeiter" ein, und WEIN tritt zum Beispiel "Für Wein ein Ist Nicht ein Emulator." GNU tritt "für GNU nicht Unix" ein.

Recursion in der Mathematik

Rekursiv definierte Sätze

Beispiel: die natürlichen Zahlen

Das kanonische Beispiel eines rekursiv definierten Satzes wird durch die natürlichen Zahlen angeführt:

:0 ist in

:if n ist darin, dann n + 1 ist in

Der:The-Satz von natürlichen Zahlen ist der kleinste Satz, der die vorherigen zwei Eigenschaften befriedigt.

Beispiel: Der Satz von wahren erreichbaren Vorschlägen

Ein anderes interessantes Beispiel ist der Satz aller "wahren erreichbaren" Vorschläge in einem axiomatischen System.

• wenn ein Vorschlag ein Axiom ist, ist es ein wahrer erreichbarer Vorschlag.
• wenn ein Vorschlag bei wahren erreichbaren Vorschlägen mittels Interferenzregeln erhalten werden kann, ist es ein wahrer erreichbarer Vorschlag.
• Der Satz von wahren erreichbaren Vorschlägen ist der kleinste Satz von Vorschlägen, die diese Bedingungen befriedigen.

Dieser Satz wird 'wahre erreichbare Vorschläge' genannt, weil in nichtkonstruktiven Annäherungen an die Fundamente der Mathematik der Satz von wahren Vorschlägen größer sein kann als der Satz, der rekursiv von den Axiomen und Regeln der Schlussfolgerung gebaut ist. Siehe auch die Unvollständigkeitslehrsätze von Gödel.

Funktioneller recursion

Eine Funktion kann in Bezug auf sich teilweise definiert werden. Ein vertrautes Beispiel ist die Fibonacci-Zahl-Folge: F (n) = F (n − 1) + F (n − 2). Für solch eine Definition, um nützlich zu sein, muss es zu Werten führen, die, in diesem Fall F (0) = 0 und F (1) = 1 nichtrekursiv definiert werden.

Eine berühmte rekursive Funktion ist die Funktion von Ackermann, die, verschieden von der Folge von Fibonacci, ohne recursion nicht leicht ausgedrückt werden kann.

Beweise, die rekursive Definitionen einschließen

Die Verwendung der Standardtechnik des Beweises durch Fälle zu rekursiv definierten Sätzen oder Funktionen, als in den vorhergehenden Abteilungen, gibt Strukturinduktion, eine starke Generalisation der mathematischen Induktion nach, die weit verwendet wird, um Beweise in der mathematischen Logik und Informatik abzuleiten.

Rekursive Optimierung

Dynamische Programmierung ist eine Annäherung an die Optimierung, die eine Mehrperiode oder Mehrschritt-Optimierungsproblem in der rekursiven Form neu formuliert. Der Schlüssel läuft auf dynamische Programmierung hinaus ist die Gleichung des Öffentlichen Ausrufers,

der den Wert des Optimierungsproblems in einer früheren Zeit (oder früherem Schritt) schreibt

in Bezug auf seinen Wert in einer späteren Zeit (oder späterem Schritt).

Recursion in der Informatik

Eine übliche Methodik der Vereinfachung ist, ein Problem in Teilprobleme desselben Typs zu teilen. Als eine Computerprogrammiertechnik wird das genannt teilen sich und siegen, und ist Schlüssel zum Design von vielen wichtigen Algorithmen. Teilen Sie und überwinden Sie Aufschläge als eine verfeinernde Annäherung an das Problem-Lösen, wo Probleme durch das Lösen kleinerer und kleinerer Beispiele behoben werden. Eine gegensätzliche Annäherung ist dynamische Programmierung. Diese Annäherung dient als von unten nach oben Annäherung, wo Probleme durch das Lösen größerer und größerer Beispiele behoben werden, bis die gewünschte Größe erreicht wird.

Ein klassisches Beispiel von recursion ist die Definition der Factorial-Funktion, gegeben hier im C-Code:

nicht unterzeichnete interne Nummer factorial (nicht unterzeichnete interne Nummer n)

{\

wenn (n

Die Funktion nennt sich rekursiv auf einer kleineren Version des Eingangs (n - 1) und multipliziert das Ergebnis des rekursiven Anrufs durch n, bis zum Erreichen des Grundfalls analog zur mathematischen Definition von factorial.

Recursion in der Computerprogrammierung wird veranschaulicht, wenn eine Funktion in Bezug auf den einfacheren, häufig kleinere Versionen von sich definiert wird. Die Lösung des Problems wird dann durch das Kombinieren der bei den einfacheren Versionen des Problems erhaltenen Lösungen ausgedacht. Eine Beispiel-Anwendung von recursion ist in parsers für Programmiersprachen. Der große Vorteil von recursion besteht darin, dass ein unendlicher Satz von möglichen Sätzen, Designs oder anderen Daten definiert, grammatisch analysiert oder durch ein begrenztes Computerprogramm erzeugt werden kann.

Wiederauftreten-Beziehungen sind Gleichungen, um eine oder mehr Folgen rekursiv zu definieren. Einige spezifische Arten der Wiederauftreten-Beziehung können "gelöst" werden, um eine nichtrekursive Definition zu erhalten.

Der Gebrauch von recursion in einem Algorithmus ist im Vorteil und Nachteile. Der Hauptvorteil ist gewöhnlich Einfachheit. Der Hauptnachteil ist häufig, dass der Algorithmus große Beträge des Gedächtnisses verlangen kann, wenn die Tiefe des recursion sehr groß ist.

Der recursion Lehrsatz

In der Mengenlehre ist das ein Lehrsatz, der versichert, dass rekursiv definierte Funktionen bestehen. In Anbetracht eines Satzes X, ein Element X und eine Funktion, stellt der Lehrsatz fest, dass es eine einzigartige Funktion gibt (wo den Satz von natürlichen Zahlen einschließlich der Null anzeigt) solch dass

für jede natürliche Zahl n.

Beweis der Einzigartigkeit

Nehmen Sie zwei Funktionen und solch dass:

wo eines Elements X zu sein.

Es kann durch die mathematische Induktion dass für alle natürlichen Zahlen n bewiesen werden:

:Base-Fall: So hält die Gleichheit dafür.

:Inductive-Schritt: Denken Sie für einige. Dann

:: Folglich F (k) = G bezieht (k) F (k+1) = G (k+1) ein.

Durch die Induktion, für alle.

Beispiele

Einige allgemeine Wiederauftreten-Beziehungen sind:

• Goldenes Verhältnis: φ = 1 + (1/φ)... sich dass φ = 1 + (1/φ) dann erinnernd... φ = 1 + (1 / (1 + (1/1+1/...)
• Factorial:
• Fibonacci-Zahlen:
• Katalanische Zahlen:
• Computerwissenschaft von Zinseszinsen
• Der Turm Hanois
• Funktion von Ackermann

Bibliografie

• - bietet eine Behandlung von corecursion an.
• , das erste Kapitel über die Mengenlehre.

Siehe auch

• Kirch-Turing-These
• Dauerndes Prädikat
• Corecursion
• Kurs Werte recursion
• Wirkung von Droste
• Fester Punkt combinator
• Unendliche Schleife
• Infinitism
• Wiederholte Funktion
• Mise en abyme
• Primitive rekursive Funktion
• Einspringend (Unterprogramm)
• Selbstverweisung
• Fremde Schleife
• Schwanz recursion
• Die Selbstverweisungsformel von Tupper
• Schildkröten den ganzen Weg unten
• Lebensfähiges Systemmodell

Links

• Recursion - Tutorenkurs durch Alan Gauld
• Eine Zündvorrichtung auf Recursion-enthält Zeigestöcke zu recursion auf Formellen Sprachen, Linguistik, Mathematik und Informatik
• Schwirren-Dateien den ganzen Weg unten
• Nevins, Andrew und David Pesetsky und Cilene Rodrigues. Beweise und Beweisführung: Eine Antwort Everett (2009). Sprache 85.3: 671 - 681 (2009)
• Kaan, E. - Swaab, T. Y. (2002) "Das Gehirnschaltsystem des syntaktischen Verständnisses", Tendenzen in Erkenntnistheorien, vol. 6, Ausgabe 8, 350-356.