WikiDer > Rekursion

Rekursion (Latein: wiederkehren, 'umgekehrt') ist das Auftreten einer Folge von Konstruktionen, von denen jede einzeln auf einer oder mehreren ähnlichen vorhergehenden Konstruktionen basiert. Normalerweise unterscheidet sich die nächste Konstruktion im Wert von der vorherigen und hat einen Ausgangspunkt. Rekursive Konstruktionen kommen einerseits in der Linguistik für und andererseits im Mathematik, Informatik und Logik.

Es ist ein Sonderfall der Rekursivität Droste-Effekt, wobei eine nachfolgende Konstruktion eine verkleinerte Ansicht der vorhergehenden ist.

Rekursion in der Linguistik

In der Linguistik tritt Rekursion in der Satzbau. Die Rekursion erfolgt dabei nicht auf der Ebene einzelner Vorkommen, sondern auf Artebene. Beispielsweise können Sätze beliebig tief in andere Sätze eingebettet werden. Beispiel:

Die Tatsache, dass deine Uhr ist kaputt heißt das nicht du kannst zu spät kommen.

Abgesehen von der abweichenden Wortstellung sind die eingebetteten Teile vollständige Sätze. Der Einbettungsprozess ist rekursiv, weil er theoretisch beliebig oft wiederholt werden kann: deine Uhr ist kaputt kann erweitert werden auf deine Uhr ist kaputtweil es gefallen ist danach fuhr ein Auto über Das ... .

Einige Linguisten glauben, dass die Rekursivität das wichtigste Element der Sprache der Menschen ist.^[1]

Ein Beispiel ist die Klausel. Ein vereinfachtes Fließband kann lesen:

1. Z → ND WD

d.h. ein Satz Z besteht aus einem Substantivteil ND und einem Verbteil WD.

2. WD → W ND*

ein Verbteil besteht aus einem Verb W und einem oder mehreren Nomenteilen als Objekt des Verbs.

3. WD → W Z

ein Verbteil besteht aus einem Verb W und einem Nebensatz als Objekt des Verbs.

Wird mit den Zeilen 1 und 3 ein Satz gebildet, so kommt es zur Rekursion, da in Zeile 3 ein weiterer Satz vorkommt.

Rekursion in der exakten Wissenschaft

sehen Differentialgleichung für die Verwendung von Rekursivität in der Mathematik, Rekursion (Informatik) für Informatik und Selbstreferenz für die Logik.

Mathematik

In dem Mathematik rekursive Funktionen verwendet werden, sind sie gegeben durch Differenzgleichungen oder synonym, wiederkehrende Beziehungen. Ein Beispiel ist die rekursive Definition von Fakultät (!) von a natürliche Zahl.

Die Anfangsbedingung ist:

${Anzeigestil 1!=1}$

Die rekursive Definition lautet:

${Anzeigestil n!=ncdot(n-1)!}$

Ein weiteres Beispiel ist die Fibonaccia-Folge:

${displaystyle f_{n}=f_{n-1} f_{n-2},,{ ext{for }}n>1}$

mit als Startwerte

${displaystyle f_{0}=0}$

${displaystyle f_{1}=1}$

Informatik

Nach diesen Definitionen sind die Fakultäts- und Fibonacci-Folge in a Computer Programm in einer rekursiven Funktion implementiert sind, ruft sich die Funktion dann selbst auf. Rekursion ist nicht alles Programmiersprachen möglich.

Natur

Rekursion kommt in der Natur häufig vor^[2]. Einige Beispiele:

• Kondensation, Kristallbildung
• Clusterbildung, Schneeballeffekt
• chemische Reaktionen unter dem Einfluss eines Katalysators (z.B. Entzündung)
• Kettenreaktion (z.B. in einer Atombombe)
• Wachstum, Zellteilung
• Selbstorganisation (z.B. Gehirnentwicklung)
• Fraktale in der Natur (z.B. Farnblatt)
• Generationenfolge

Im Allgemeinen führt die Rekursion in der Natur zu einem höheren Grad an Ordnung und/oder Komplexität, so dass die Entropie lokal abnimmt (makroskopisch jedoch zunimmt). auftauchend wenn es Merkmale hat, die in früheren Generationen nicht vorhanden waren. Grundsätzlich kann der rekursive Prozess unbegrenzt fortgesetzt werden, sofern die Bedingungen (die Voraussetzungen, z freie Energie) lässt das zu. Die Entstehung eines rekursiven Prozesses kann auch als a . beschrieben werden auftauchend Phänomen werden wahrgenommen^[3].

Rekursive Akronyme

Etwas Abkürzungen rekursiv definiert sind, kommt das Akronym in der Bedeutung zurück:

• GNU: GNU ist nicht Unix
• Wein: Wein ist kein Emulator
• PHP: PHP: Hypertext-Präprozessor
• LAME: Lame ist kein MP3-Encoder