Rekursion - Recursion

Eine visuelle Form der Rekursion, die als Droste-Effekt bekannt ist . Die Frau in diesem Bild hält ein Objekt, das ein kleineres Bild von ihr enthält, das ein identisches Objekt hält, das wiederum ein kleineres Bild von sich selbst enthält, das ein identisches Objekt hält, und so weiter. 1904 Droste Kakaodose , Entwurf Jan Misset

Rekursion (Adjektiv: rekursiv ) tritt auf, wenn ein Ding in Bezug auf sich selbst oder seinen Typ definiert ist. Rekursion wird in einer Vielzahl von Disziplinen verwendet, von der Linguistik bis zur Logik . Die häufigste Anwendung der Rekursion findet sich in der Mathematik und Informatik , wo eine zu definierende Funktion innerhalb ihrer eigenen Definition angewendet wird. Dies definiert zwar scheinbar unendlich viele Instanzen (Funktionswerte), wird aber oft so gemacht, dass keine Endlosschleife oder unendliche Verweiskette auftreten kann.

Formale Definitionen

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

In der Mathematik und Informatik zeigt eine Klasse von Objekten oder Methoden rekursives Verhalten, wenn sie durch zwei Eigenschaften definiert werden kann:

  • Ein einfacher Basisfall (oder einfache Fälle) – ein abschließendes Szenario, das keine Rekursion verwendet, um eine Antwort zu erzeugen
  • Ein rekursiver Schritt – ein Satz von Regeln, der alle aufeinanderfolgenden Fälle auf den Basisfall reduziert.

Das Folgende ist beispielsweise eine rekursive Definition des Vorfahren einer Person . Einer der Vorfahren ist entweder:

  • Elternteil ( Basisfall ) oder
  • Vorfahren der Eltern ( rekursiver Schritt ).

Die 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 ganzen Zahlen n > 1 gilt Fib( n ) = Fib( n − 1) + Fib( n − 2) .

Viele mathematische Axiome basieren auf rekursiven Regeln. Zum Beispiel kann die formale Definition der natürlichen Zahlen durch die Peano-Axiome wie folgt beschrieben werden: "Null ist eine natürliche Zahl, und jede natürliche Zahl hat einen Nachfolger, der auch eine natürliche Zahl ist." Durch diesen Basisfall und die rekursive Regel kann man die Menge aller natürlichen Zahlen erzeugen.

Andere rekursiv definierte mathematische Objekte umfassen Fakultäten , Funktionen (zB Rekursionsbeziehungen ), Mengen (zB Cantor ternäre Menge ) und Fraktale .

Es gibt verschiedene augenzwinkerndere Definitionen von Rekursion; siehe rekursiven Humor .

Informelle Definition

Frisch aufgefrischter Sauerteig , der durch die Gärung sprudelt : Das Rezept verlangt etwas Sauerteig, der von der letzten Herstellung des gleichen Rezepts übrig geblieben ist.

Rekursion ist der Prozess, den eine Prozedur durchläuft, wenn einer der Schritte der Prozedur das Aufrufen der Prozedur selbst beinhaltet. Ein rekursives Verfahren wird als „rekursiv“ bezeichnet.

Um Rekursion zu verstehen, muss man den Unterschied zwischen einer Prozedur und dem Ablauf einer Prozedur erkennen. Ein Verfahren ist ein Satz von Schritten, der auf einem Satz von Regeln basiert, während das Ausführen eines Verfahrens das tatsächliche Befolgen der Regeln und das Ausführen der Schritte beinhaltet.

Rekursion bezieht sich auf einen Verweis innerhalb der Spezifikation einer Prozedur auf die Ausführung einer anderen Prozedur, ist aber nicht dasselbe.

Wenn eine Prozedur als solche definiert ist, entsteht sofort die Möglichkeit einer Endlosschleife; Rekursion kann nur dann sinnvoll in einer Definition verwendet werden, wenn der betreffende Schritt in bestimmten Fällen übersprungen wird, damit die Prozedur abgeschlossen werden kann.

Aber selbst wenn es richtig definiert ist, ist ein rekursives Verfahren für den Menschen nicht einfach durchzuführen, da es erfordert, den neuen vom alten, teilweise ausgeführten Aufruf des Verfahrens zu unterscheiden; dies erfordert eine gewisse Verwaltung, wie weit verschiedene gleichzeitige Instanzen der Verfahren fortgeschritten sind. Aus diesem Grund sind rekursive Definitionen im Alltag sehr selten.

In Sprache

Der Linguist Noam Chomsky hat unter anderem argumentiert, dass das Fehlen einer Obergrenze für die Anzahl grammatikalischer Sätze in einer Sprache und das Fehlen einer Obergrenze für die grammatikalische Satzlänge (außerhalb praktischer Beschränkungen wie der Zeit, die zum Aussprechen eines Satzes zur Verfügung steht) ), kann als Folge der Rekursion in natürlicher Sprache erklärt werden.

Dies kann im Sinne einer rekursiven Definition einer syntaktischen Kategorie, beispielsweise eines Satzes, verstanden werden. Ein Satz kann eine Struktur haben, in der auf das Verb ein anderer Satz folgt: Dorothy hält Hexen für gefährlich , wobei der Satz Hexen sind gefährlich im größeren Satz vorkommt. So kann ein Satz rekursiv (sehr grob) als etwas mit einer Struktur definiert werden, die eine Nominalphrase, ein Verb und optional einen weiteren Satz enthält. Dies ist eigentlich nur ein Sonderfall der mathematischen Definition der Rekursion.

Dies bietet eine Möglichkeit, die Kreativität der Sprache – die unbegrenzte Anzahl grammatikalischer Sätze – zu verstehen, da sie sofort voraussagt, dass Sätze beliebig lang sein können: Dorothy glaubt, dass Toto vermutet, dass Tin Man 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. Im Laufe der Jahre haben sich Sprachen im Allgemeinen für diese Art der Analyse als zugänglich erwiesen.

In letzter Zeit wurde jedoch die allgemein akzeptierte Vorstellung, dass Rekursion eine wesentliche Eigenschaft der menschlichen Sprache sei, von Daniel Everett aufgrund seiner Behauptungen über die Pirahã-Sprache in Frage gestellt . Andrew Nevins, David Pesetsky und Cilene Rodrigues sind unter vielen, die sich dagegen ausgesprochen haben. Literarische Selbstreferenz kann in jedem Fall als etwas anderes argumentiert werden als mathematische oder logische Rekursion.

Rekursion spielt nicht nur in der Syntax, sondern auch in der Semantik natürlicher Sprache eine entscheidende Rolle . Das Wort und kann zum Beispiel als eine Funktion ausgelegt werden, die auf Satzbedeutungen angewendet werden kann, um neue Sätze zu erzeugen, und ebenso auf Nominalphrasenbedeutungen, Verbphrasenbedeutungen und andere. Es kann auch auf intransitive Verben, transitive Verben oder ditransitive Verben angewendet werden. Um eine einzige Bezeichnung dafür bereitzustellen, die entsprechend flexibel ist und typischerweise so definiert ist, dass sie jede dieser verschiedenen Arten von Bedeutungen als Argumente annehmen kann. Dies kann erreicht werden, indem es für einen einfachen Fall definiert wird, in dem es Sätze kombiniert, und dann die anderen Fälle rekursiv in Bezug auf den einfachen Fall definiert.

Eine rekursive Grammatik ist eine formale Grammatik, die rekursive Produktionsregeln enthält .

Rekursiver Humor

Eine rekursive Wikipedia- Seite

Rekursion wird in Informatik-, Programmier-, Philosophie- oder Mathematik-Lehrbüchern manchmal humorvoll verwendet, im Allgemeinen durch eine zirkuläre Definition oder Selbstreferenz , bei der der mutmaßliche rekursive Schritt einem Basisfall nicht näher kommt, sondern stattdessen zu einem unendlichen Regress führt . Es ist nicht ungewöhnlich, dass solche Bücher in ihrem Glossar einen Witzeintrag nach dem folgenden Muster enthalten:

Rekursion, siehe Rekursion .

Eine Variation findet sich auf Seite 269 im Index einiger Ausgaben von Brian Kernighan und Dennis Ritchies Buch The C Programming Language ; der Indexeintrag verweist rekursiv auf sich selbst ("Rekursion 86, 139, 141, 182, 202, 269"). Frühe Versionen dieses Witzes finden sich in Let's talk Lisp von Laurent Siklóssy (veröffentlicht von Prentice Hall PTR am 1. Dezember 1975, Copyright-Datum 1976) und in Software Tools von Kernighan und Plauger (veröffentlicht von Addison-Wesley Professional on 11. Januar 1976). Der Witz taucht auch in The UNIX Programming Environment von Kernighan und Pike auf. Es erschien nicht in der ersten Ausgabe von The C Programming Language . Der Witz gehört zur Folklore der funktionalen Programmierung und war bereits vor der Veröffentlichung der oben genannten Bücher in der Community der funktionalen Programmierung weit verbreitet.

Ein anderer Witz lautet: "Um Rekursion zu verstehen, muss man Rekursion verstehen." In der englischsprachigen Version der Google-Websuchmaschine wird bei einer Suche nach "rekursion" die Seite "Meinten Sie: rekursion " vorgeschlagen. Eine alternative Form ist die folgende von Andrew Plotkin : "Wenn Sie bereits wissen, was Rekursion ist, erinnern Sie sich einfach an die Antwort. Andernfalls finden Sie jemanden, der Douglas Hofstadter näher steht als Sie; dann fragen Sie ihn oder sie, was Rekursion ist."

Rekursive Akronyme sind weitere Beispiele für rekursiven Humor. PHP steht beispielsweise für "PHP Hypertext Preprocessor", WINE steht für "WINE Is Not an Emulator", GNU steht für "GNU's not Unix" und SPARQL bezeichnet das "SPARQL Protocol and RDF Query Language".

In Mathematik

Das Sierpinski-Dreieck – eine begrenzte Rekursion von Dreiecken, die ein Fraktal bilden

Rekursiv definierte Mengen

Beispiel: die natürlichen Zahlen

Das kanonische Beispiel einer rekursiv definierten Menge ist durch die natürlichen Zahlen gegeben :

0 ist in
wenn n in ist , dann ist n + 1 in
Die Menge der natürlichen Zahlen ist die kleinste Menge, die die beiden vorherigen Eigenschaften erfüllt.

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

Beispiel: Nachweisverfahren

Ein weiteres interessantes Beispiel ist die Menge aller "beweisbaren" Aussagen in einem axiomatischen System , die durch ein induktiv (oder rekursiv) definiertes Beweisverfahren wie folgt definiert sind:

  • Wenn ein Satz ein Axiom ist, ist er ein beweisbarer Satz.
  • Wenn ein Satz mittels Inferenzregeln aus echten erreichbaren Sätzen abgeleitet werden kann, ist er ein beweisbarer Satz.
  • Die Menge beweisbarer Aussagen ist die kleinste Menge von Aussagen, die diese Bedingungen erfüllen.

Endliche Unterteilungsregeln

Finite Unterteilungsregeln sind eine geometrische Form der Rekursion, mit der fraktalähnliche Bilder erstellt werden können. Eine Unterteilungsregel beginnt mit einer Sammlung von Polygonen, die mit endlich vielen Beschriftungen beschriftet sind, und dann wird jedes Polygon in kleinere beschriftete Polygone unterteilt, die nur von den Beschriftungen des ursprünglichen Polygons abhängt. Dieser Vorgang kann wiederholt werden. Die Standardtechnik des `mittleren Drittels' zum Erstellen der Cantor-Menge ist eine Unterteilungsregel, ebenso wie die baryzentrische Unterteilung .

Funktionale Rekursion

Eine Funktion kann in Bezug auf sich selbst rekursiv definiert werden. Ein bekanntes Beispiel ist die Fibonacci- Zahlenfolge: F ( n ) = F ( n − 1) + F ( n − 2). Damit eine solche Definition sinnvoll 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 , die im Gegensatz zur Fibonacci-Folge nicht ohne Rekursion ausgedrückt werden kann.

Beweise mit rekursiven Definitionen

Die Anwendung der Standardtechnik des Beweises durch Fälle auf rekursiv definierte Mengen oder Funktionen, wie in den vorherigen Abschnitten, führt zu einer strukturellen Induktion – einer mächtigen Verallgemeinerung der mathematischen Induktion , die in der mathematischen Logik und Informatik weit verbreitet ist, um Beweise abzuleiten .

Rekursive Optimierung

Dynamische Programmierung ist ein Optimierungsansatz , der ein Mehrperioden- oder Mehrschritt-Optimierungsproblem in rekursiver Form wiedergibt. Das Schlüsselergebnis der dynamischen Programmierung ist die Bellman-Gleichung , die 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äteren Schritt) schreibt.

Der Rekursionssatz

In der Mengenlehre ist dies ein Satz, der garantiert, dass rekursiv definierte Funktionen existieren. Gegeben eine Menge X , ein Element a von X und eine Funktion f : XX , besagt der Satz, dass es eine eindeutige Funktion (wobei bezeichnet die Menge der natürlichen Zahlen einschließlich Null) gibt mit

für jede natürliche Zahl n .

Nachweis der Einzigartigkeit

Nehmen Sie zwei Funktionen und so, dass:

wobei a ein Element von X ist .

Durch mathematische Induktion lässt sich beweisen, dass F ( n ) = G ( n ) für alle natürlichen Zahlen n gilt :

Basisfall : F (0) = a = G (0) also gilt die Gleichheit für n = 0 .
Induktiver Schritt : Angenommen F ( k ) = G ( k ) für einige . Dann ist F ( k +1) = f ( F ( k )) = f ( G ( k )) = G ( k +1) .
Daher impliziert F ( k ) = G ( k ) F ( k +1) = G ( k +1) .

Durch Induktion ist F ( n ) = G ( n ) für alle .

In der Informatik

Eine gängige Methode zur Vereinfachung besteht darin, ein Problem in Teilprobleme desselben Typs aufzuteilen. Als Computerprogrammiertechnik wird dies Teilen und Herrschen genannt und ist der Schlüssel zum Entwurf vieler wichtiger Algorithmen. Divide and Conquer dient als Top-Down-Ansatz zur Problemlösung, bei dem Probleme durch die Lösung immer kleinerer Instanzen gelöst werden. Ein gegenteiliger Ansatz ist die dynamische Programmierung . Dieser Ansatz dient als Bottom-up-Ansatz, bei dem Probleme durch die Lösung immer größerer Instanzen gelöst werden, bis die gewünschte Größe erreicht ist.

Ein klassisches Beispiel für Rekursion ist die Definition der Fakultätsfunktion , hier im C- Code:

unsigned int factorial(unsigned int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

Die Funktion ruft sich rekursiv mit einer kleineren Version der Eingabe auf (n - 1)und multipliziert das Ergebnis des rekursiven Aufrufs mit n, bis der Basisfall erreicht ist , analog zur mathematischen Definition von Fakultät.

Rekursion in der Computerprogrammierung wird veranschaulicht, wenn eine Funktion in Bezug auf einfachere, oft kleinere Versionen ihrer selbst definiert wird. Die Lösung des Problems wird dann durch Kombinieren der aus den einfacheren Versionen des Problems erhaltenen Lösungen entwickelt. Eine Beispielanwendung der Rekursion sind Parser für Programmiersprachen. Der große Vorteil der Rekursion besteht darin, dass eine unendliche Menge möglicher Sätze, Designs oder anderer Daten von einem endlichen Computerprogramm definiert, geparst oder erzeugt werden kann.

Rekursionsbeziehungen sind Gleichungen, die eine oder mehrere Sequenzen rekursiv definieren. Einige spezifische Arten von Rekursionsbeziehungen können "gelöst" werden, um eine nicht-rekursive Definition zu erhalten (z. B. einen Ausdruck in geschlossener Form ).

Die Verwendung der Rekursion in einem Algorithmus hat sowohl Vor- als auch Nachteile. Der Hauptvorteil ist normalerweise die Einfachheit der Anweisungen. Der Hauptnachteil besteht darin, dass die Speichernutzung rekursiver Algorithmen sehr schnell ansteigen kann, was sie für größere Instanzen unpraktisch macht.

In Biologie

Formen, die durch rekursive Prozesse entstanden zu sein scheinen, treten manchmal bei Pflanzen und Tieren auf, beispielsweise bei verzweigten Strukturen, bei denen sich ein großer Teil in zwei oder mehr ähnliche kleinere Teile verzweigt. Ein Beispiel ist Romanesco-Brokkoli .

In Kunst

Rekursive Puppen: der Originalsatz der Matroschka-Puppen von Zvyozdochkin und Malyutin , 1892
Vorderseite Giotto ‚s Stefaneschi Triptych , 1320, enthält rekursiv ein Bild von sich selbst (durch die kniende Figur in der mittleren Platte gehalten).

Die russische Puppe oder Matrjoschka-Puppe ist ein physisches künstlerisches Beispiel für das rekursive Konzept.

Rekursion wurde in Gemälden seit verwendet Giotto ‚s Stefaneschi Triptychon , made in 1320. Die zentrale Platte enthält die kniende Figur des Kardinals Stefaneschi, hält das Triptychon selbst als Opfer.

MC Escher ‚s Print Gallery (1956) ist ein Druck , der eine verzerrte Stadt , die eine Galerie zeigt die rekursiv das Bild enthält, und so ad infinitum .

Siehe auch

Verweise

Literaturverzeichnis

Externe Links