Quelltext der Seite Rekursion

{{Dieser Artikel|behandelt den grundlegenden Vorgang Rekursion: Anwendungsbeispiel ist die ''[[rekursive Definition]]'' in der Mathematik; zum Begriff ''rekursive Menge'' siehe [[Entscheidbar]].}}

Als '''Rekursion''' ({{laS|recurrere|de=zurücklaufen}}) wird ein prinzipiell unendlicher Vorgang bezeichnet, der sich selbst als Teil enthält oder mithilfe von sich selbst definierbar ist.<ref>[[Niklaus Wirth]], Seite 149: 3. Rekursion, 3.1. Einleitung</ref> Üblicherweise sind rekursive Vorgänge relativ kurz beschreibbar bzw. können durch eine relativ kurze Anweisung ausgelöst werden.<ref>Niklaus Wirth: ''Algorithmen und Datenstrukturen''. B. G. Teubner 1983, Seite 150: „Das Wesentliche der Rekursion ist die Möglichkeit, eine unendliche Menge von Objekten durch eine endliche Aussage zu definieren.“</ref><ref name="Buss"/> Die bei Rekursion aufeinander folgenden Teilvorgänge oder die nacheinander erzeugten Objekte sind nicht unabhängig voneinander, sondern zwischen jedem Schrittpaar oder Objektpaar besteht eine besondere, die ''rekursive'' Beziehung.

„Der Begriff [Rekursion] ist sehr umfassend.“<ref>[[Douglas R. Hofstadter]]: ''Gödel, Escher, Bach''. dtv, 2004, Seite 137.</ref> In der Natur handelt es sich um einen häufig beobachtbaren Vorgang (z.&nbsp;B. beim [[Blumenkohl#Formen und Typen|Pflanzenwachstum]] oder Blüten). In vielen Bereichen der [[Kultur]] wird er nachgebildet, so in den [[Kunst|schönen Künsten]], wo das Phänomen u.&nbsp;a. als [[Mise en abyme]] bezeichnet wird. In [[Mathematik]] und [[Informatik]] ist ‚Rekursion‘ ein gängiger Begriff.

Rekursion ist auch eine Problemlösungsstrategie. Komplexe Sachverhalte können oft mit rekursiv formulierten Regeln sehr elegant erfasst werden. Das Grundprinzip ist dabei dann das Zurückführen einer allgemeinen Aufgabe auf eine einfachere Aufgabe derselben Klasse. Das wird u.&nbsp;a. auch beim sogenannten [[rekursive Programmierung|rekursiven Programmieren]] genutzt: Um Rekursion entstehen zu lassen, muss eine [[Prozedur (Programmierung)|Prozedur]], [[Funktion (Informatik)|Funktion]] oder [[Unterprogramm#Terminologie|Methode]] lediglich sich selbst [[Methode (Programmierung)#Methodenaufruf|aufrufen]]. Dieser Prozess läuft weiter, bis eine im Programm enthaltene Abbruchbedingung greift.

In der Mathematik wird das rekursive Formulieren mit Vorteil zur Definition von Funktionen angewendet (siehe [[Rekursive Definition]]).

== {{Anker|Beispiele}}Einführende Beispiele für Rekursion ==
=== Rekursive Grafiken ===
[[Datei:Pythagoras baum Filled.png|mini|[[Pythagoras-Baum]]]]
[[Datei:Pythagoras tree construct 4of5.png|mini|„Sprießender“ Pythagoras-Baum]]

Rekursive Regeln können in der Erstellung von Grafiken verwendet werden, dies ergibt die sogenannten [[Fraktal]]e&nbsp;– ästhetisch ansprechende, ''natürlich'' aussehende Gebilde. Ein Beispiel ist der [[Pythagoras-Baum]]. Er entsteht nach folgender Regel (der dritte Schritt zeigt die Rekursion):
* Errichte auf einer gegebenen Grundlinie ein ''Quadrat''.
* Auf seiner Oberseite zeichne ein ''Dreieck'' mit vorgegebenen Winkeln bzw. Höhe.
* Wende die beiden obigen Schritte jeweils erneut auf die beiden freien Seiten des neuentstandenen Dreieckes an.
Dieser [[Algorithmus]] wird dann bis zu einer vorgegebenen ''Rekursionstiefe'' entfaltet; wird er einmal durchlaufen, entsteht ein Dreieck mit je einem Quadrat über den drei Seiten. Das sieht wie die Illustration zum [[Satz des Pythagoras]] aus&nbsp;– daher der Name. Je größer die Rekursionstiefe wird, desto mehr ähnelt das Gebilde einem Baum.

Man kann die beiden ersten Schritte in der obigen Beschreibung überspringen und den rekursiven Prozess mit der Illustration zum Satz des Pythagoras beginnen:
* Erzeuge aus dieser Illustration zwei weitere, ihr [[Ähnlichkeit (Geometrie)|ähnliche]] Illustrationen, deren jeweiliges Hypotenusen-''Quadrat'' identisch mit einem der beiden Katheten-''Quadrate'' der vorherigen Illustration ist.
* Erzeuge nach gleicher Vorschrift aus jeder der im ersten Schritt erzeugten Illustrationen jeweils zwei weitere ihnen ähnliche Illustrationen usw.

=== Rekursion in der Grammatik ===
Die [[Grammatik]] [[Natürliche Sprache|natürlicher Sprachen]] wird in der [[Linguistik]] u.&nbsp;a. mit Hilfe von sogenannten [[Produktionsregel#Linguistik|Phrasenstrukturregeln]] beschrieben.<ref>Siehe z.&nbsp;B. Andrew Carnie: ''Constituent Structure.'' Second edition. Oxford University Press, 2010. Zum Thema Rekursivität v.&nbsp;a. S. 84ff.</ref> Nach Ansicht der meisten Linguisten zeigen dabei alle menschlichen Sprachen<ref>Lediglich für die Sprache [[Pirahã]] ist die These vorgebracht worden, dass sie keine Rekursion in der Grammatik kennen würde, da es keine Nebensätze gebe. Diese Analyse ist umstritten, für Details siehe den verlinkten Artikel.</ref> die Eigenschaft, rekursiv aufgebaut zu sein (im Gegensatz zu Signalsystemen im Tierreich). Dies ergibt sich, weil in der Zerlegung einer grammatischen Einheit, die mit einer Kategorie etikettiert wird, dieselbe Kategorie erneut auftauchen kann. Ein Beispiel ist das Phänomen der [[Nebensatz|Nebensätze]], das hier mit folgender stark vereinfachter Produktionsregel beschrieben ist:

# S → NP VP (ein Satz besteht aus einer [[Nominalphrase]] (als Subjekt) und einer [[Verbalphrase]])
# VP → V NP* (eine Verbalphrase besteht aus einem Verb und null bis vielen Nominalphrasen als Objekten des Verbs)
# VP → V S (eine Verbalphrase besteht aus einem Verb und einem Nebensatz als Objekt des Verbs)

Diese Grammatik lässt die Wahl, ob die Ausbuchstabierung von „VP“ mit Regel 2 oder 3 erfolgen soll. Für den Fall, dass die Schritte 1 und dann 3 aufgerufen werden, ergibt sich eine Rekursion: Als Produkt von Regel 3 erscheint das Symbol S, das wiederum den Start für Regel 1 darstellt.<ref name="Buss">[[Hadumod Bußmann]] (Hrsg.): ''Lexikon der Sprachwissenschaft.'' Alfred Kröner Verlag, Stuttgart 1990, S. 640: ''Rekursion ist in der Linguistik ein Begriff, “der die formale Eigenschaft von Grammatiken bezeichnet, mit einem endlichen Inventar von Elementen und einer endlichen Menge von Regeln eine unendliche Menge von Sätzen zu erzeugen.”'' (zitiert neben Beispielen aus Sprache, Natur, Kunst und Dichtung Mathematik und Programmierung, u.&nbsp;a.  z.&nbsp;B. in uni-leipzig: [https://home.uni-leipzig.de/heck/recursion08/einfuehrung2.pdf ''Rekursion in der Sprache'']).</ref> Wenn die Regel 2 aufgerufen wird, ergibt sich ebenfalls eine Rekursion, nämlich über das Symbol NP.

=== Rekursion in der Mathematik ===
In der Mathematik spielt Rekursion eine große Rolle, zum Beispiel in der [[Definition#Rekursive Definition|rekursiven Definition]] von Funktionen. Als Beispiele werden im Folgenden die Berechnung der ''Fakultät'' und die ''Fibonacci-Folge'' dargestellt. Rekursionsverfahren und rekursive Definition sind in der Mathematik aber nicht auf Funktionen [[natürliche Zahlen|natürlicher Zahlen]] beschränkt.

Konzeptionell nahe verwandt ist der „Nachfolger“ in den [[Peano-Axiome]]n und die Beweismethode der [[Vollständige Induktion|vollständigen Induktion]].

==== Fakultät ====
Die Funktion [[Fakultät (Mathematik)|Fakultät]] einer natürlichen Zahl <math>n \geq 1</math> ist definiert als das Produkt der Zahlen 1 bis <math>n</math>:
: <math>n! = 1\cdot 2 \cdot 3 \dotsm n = \prod_{k=1}^n k</math>
Beispiele
:<math>\begin{array}{rll}
1! &= 1 &= 1\\
2! &= 1 \cdot 2 & = 2\\
3! &= 1 \cdot 2 \cdot 3 & = 6\\
4! &= 1 \cdot 2 \cdot 3 \cdot 4 & = 24\\
\end{array}</math>
Soll diese Liste fortgesetzt werden, ergibt sich die Rekursivität nahezu von selbst.
Für die Berechnung von 5! wird man nicht von vorn beginnen, sondern kann auf vorherige Ergebnisse zurückgreifen, also
: <math>5! = 4! \cdot 5 = 120 </math>

Verallgemeinert lässt sich die Funktion somit ''rekursiv'' definieren:
:<math>n! = \left\{\begin{matrix}
1 && \text{falls } n = 1   && \text{(Rekursionsanfang)} \\
(n-1)! \cdot n && \text{sonst} && \text{(Rekursionsschritt)}
\end{matrix}\right.</math>

==== Die Fibonacci-Folge ====
Ein klassisches Beispiel für eine rekursive Funktion ist die [[Fibonacci-Folge]], bei der jedes weitere Folgenglied die Summe der beiden vorhergehenden ist:
:<math>0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \dotsc</math>

Im Gegensatz zur Fakultätsfunktion ist für die Fibonacci-Folge keine kompakte geschlossene Form definiert worden.
Die einfachste Beschreibung ist die rekursive Definition:

:<math>\operatorname{fib}(n) = \left\{\begin{matrix}
0                         && \text{falls } n = 0   && \text{(Rekursionsanfang)} \\
1                         && \text{falls } n = 1   && \text{(Rekursionsanfang)} \\
\operatorname{fib}(n-1)+\operatorname{fib}(n-2) && \text{sonst} && \text{(Rekursionsschritt)}
\end{matrix}\right.</math>

Diese rekursive Definition ist kaskadenförmig. Die dritte Fibonacci-Zahl wird anhand dieser Definition folgendermaßen berechnet:
:<math>\begin{matrix}
\operatorname{fib}(3) & = & \operatorname{fib}(2)+\operatorname{fib}(1)    & \text{(Rekursionsschritt)} \\
                      & = & \operatorname{fib}(1)+\operatorname{fib}(0)+\operatorname{fib}(1)    & \text{(Rekursionsschritt)} \\
                      & = & 1+\operatorname{fib}(0)+\operatorname{fib}(1) & \text{(Rekursionsanfang)} \\
                      & = & 1+0+\operatorname{fib}(1)                     & \text{(Rekursionsanfang)} \\
                      & = & 1+0+1                     & \text{(Rekursionsanfang)} \\
                      & = & 2
\end{matrix}</math>
Die Berechnung für <math>\operatorname{fib}(1)</math> wird hier mehrfach durchgeführt. Das deutet an, dass es Potential für Optimierungen gibt.
<!--PASST DAS HIER NOCH HER?
==== Insgesamt zur rekursiven Definition einer Funktion ====

Das Grundprinzip der rekursiven [[Definition]] einer Funktion ''f'' ist also: Der Funktionswert ''f''(''n''+1) einer Funktion ''f'' : '''N<sub>0</sub>''' → '''N<sub>0</sub>''' ergibt sich durch [[Verknüpfung (Mathematik)|Verknüpfung]] bereits berechneter Werte ''f''(''n''), ''f''(''n''-1), …
Falls die Funktionswerte von ''f'' für hinreichend viele Startargumente bekannt sind, kann jeder Funktionswert von ''f'' berechnet werden. Bei einer rekursiven Definition einer Funktion ''f'' ruft sich die Funktion so oft selbst auf, bis eine durch den Aufruf der Funktion veränderte Variable einen vorgegebenen Zielwert erreicht oder Grenzwert überschritten hat (Terminierung, Abbruchbedingung).
-->

== {{Anker|wechselseitig}} Formale Typen von Rekursion ==

Die häufigste Rekursionsform ist die ''lineare Rekursion'', bei der in jedem Fall der rekursiven Definition höchstens ein rekursiver Aufruf vorkommen darf. Die Berechnung verläuft dann entlang einer Kette von Aufrufen. Bei einer solchen Rekursion enthält der Aufrufbaum also keine Verzweigungen.

Die [[Primitiv-rekursive Funktion|primitive Rekursion]] ist ein Spezialfall der linearen Rekursion, der stets durch eine [[Iteration]] ersetzt werden kann (siehe unten [[#Zum Verhältnis von Rekursion und Iteration]]). Hier definiert man Funktionen auf den natürlichen Zahlen, wobei in jedem rekursiven Aufruf dessen erster Parameter um Eins ab- oder zunimmt. Jede primitiv-rekursive Definition kann unter Zuhilfenahme eines [[Stapelspeicher|Stapels]] durch eine [[Schleife (Programmierung)|Schleife]] (z.&nbsp;B. [[For-Schleife]] oder [[While-Schleife]]) ersetzt werden.

Die ''endständige'' oder ''repetitive'' Rekursion (''Tail Recursion'' oder [[Endrekursion]]) bezeichnet den Spezialfall der linearen Rekursion, bei der jeder rekursive Aufruf die letzte Aktion des rekursiven Aufrufs ist. Endrekursionen lassen sich durch [[While-Schleife]]n ersetzen und umgekehrt. (Im Gegensatz zur Endrekursion steht die ''Head Recursion''; siehe unter [[Infiniter Regress]].)

Unter ''verschachtelter'' Rekursion versteht man eine Rekursion, bei welcher rekursive Aufrufe in Parameterausdrücken rekursiver Aufrufe vorkommen. Diese Rekursionsform gilt als außerordentlich schwer zu durchschauen.

''Kaskadenförmige'' Rekursion bezeichnet den Fall, in dem mehrere rekursive Aufrufe nebeneinander stehen. Die rekursiven Aufrufe bilden dann einen Baum. Kaskadenförmige Rekursion gilt als elegant, kann aber ohne weitere Maßnahmen einen exponentiellen Berechnungsaufwand nach sich ziehen. Sie wird gerne als Ausgangspunkt für die Ableitung einer anderen, effizienteren Formulierung gebraucht.

Die ''wechselseitige'' Rekursion bezeichnet die Definition mehrerer Funktionen durch wechselseitige Verwendung voneinander. Sie lässt sich auf die gewöhnliche Rekursion einer tupelwertigen Funktion zurückführen.

== Rekursion in der Programmierung ==
[[Höhere Programmiersprache]]n, die mit [[Funktion (Programmierung)|Funktionen]] arbeiten, erlauben üblicherweise auch die Rekursion. Zumeist lassen sich Lösungen rekursiv oder iterativ angeben.

=== Zum Verhältnis von Rekursion und Iteration ===
{{Siehe auch|Rekursive Programmierung|Iterative Programmierung}}

Rekursion und [[Iteration]] sind im Wesentlichen gleich mächtige Vorgehensweisen. Gleiche oder ähnliche Vorgänge werden mehrfach wiederholt, der Unterschied liegt im verwendeten [[Algorithmus]].

Bei einer Iteration lautet der aus mehreren Teilen bestehende Befehl, mehrfach Schleifen (''for, while'' ...) zu durchlaufen, bis eine Abbruchbedingung erfüllt ist. Bei einer Rekursion genügt es, lediglich die [[Prozedur (Programmierung)|Prozeduren]] oder [[Funktion (Programmierung)|Funktionen]] mit der Aufforderung zu ergänzen, dass sie mit einem regelmäßig geänderten Parameter erneut anzuwenden sind, bis eine Abbruchbedingung erfüllt ist.

Eine Rekursion kommt i. d. R. mit weniger Quellcode aus und ist (für erfahrene Anwender) übersichtlicher – es müssen dann keine Hilfsvariablen und Schleifenzähler definiert werden. In der Abarbeitung sind iterative Verfahren meist [[Effizienz (Informatik)|effizienter]] und benötigen weniger Speicherplatz. Grund ist das Ablegen der wiederholten Funktionsaufrufe mit allen zwischengespeicherten Werten auf dem [[Stapelspeicher]] (Stack). Insbesondere kann die Rekursion auch einen [[Pufferüberlauf]] (Stack Overflow) verursachen. Bei der Programmierung von [[Echtzeitsystem]]en auf [[Mikrocontroller]]n wird daher häufig auf Rekursion verzichtet.

Manche [[Programmiersprache]]n (zum Beispiel in der [[Funktionale Programmierung|Funktionalen Programmierung]]) erlauben keine Iteration, sodass immer die rekursive Umsetzung gewählt werden muss. Solche Sprachen setzen zur Optimierung häufig primitive Rekursionen ein, die intern als Iterationen umgesetzt sind (einige Interpreter für LISP und Scheme verfahren so).

Es ist zu beachten, dass eine naive Implementierung bei manchen Funktionen (z.&nbsp;B. den [[Fibonacci-Folge|Fibonacci-Zahlen]]) bedingt, dass Teillösungen mehrfach berechnet werden. Abhilfe schafft in diesem Beispiel die [[Memoisation]], die auf der Wiederverwendung bereits berechneter Zwischenlösungen beruht. Die Rekursion ist ein wesentlicher Bestandteil einiger Entwurfsstrategien für [[Effizienz (Informatik)|effiziente]] [[Algorithmus|Algorithmen]], insbesondere der [[Teile und herrsche (Informatik)|Teile-und-herrsche]]-Strategie ''(Divide and Conquer)''. Andere Ansätze (zum Beispiel sogenannte [[Greedy-Algorithmus|Greedy-Algorithmen]]) verlangen ein iteratives Vorgehen. Rekursion und [[primitiv-rekursive Funktion]]en spielen eine große Rolle in der [[Theoretische Informatik|theoretischen Informatik]], insbesondere in der [[Komplexitätstheorie]] und [[Berechenbarkeitstheorie]] (siehe auch [[Lambda-Kalkül]] und [[Ackermannfunktion]]).

Im [[Compiler]]bau ist der [[Rekursiver Abstieg|rekursive Abstieg]] ''(Recursive Descent)'' eine Technik, bei der eine [[Formale Sprache|Sprache]] rekursiv ''[[Parser|geparst]]'' wird.

=== Programmierbeispiele ===
Das folgende Beispiel zeigt eine einfache und beliebte Implementierung der [[Fakultät (Mathematik)|Fakultätsfunktion]] in der Programmiersprache [[Python (Programmiersprache)|Python]]. Der rekursiven Variante wird hier zur Verdeutlichung eine iterative Variante gegenübergestellt. Die Rekursion kommt dadurch zum Ausdruck, dass die Funktion sich selbst mit einem um 1 verringerten Argument aufruft. Beide Implementierungen führen den Algorithmus mit linearer [[Laufzeitkomplexität]] in Abhängigkeit zum Eingabeparameter aus. Während die [[Platzkomplexität]] bei der iterativen Variante konstant bleibt, wächst der Speicherbedarf bei der rekursiven Variante linear an, da bei jedem rekursiven Funktionsaufruf ein neuer Speicherbereich für die lokalen Variablen und die Rücksprungadresse reserviert werden muss. Bei der funktionalen Programmierung wird die dynamische Speicherverwaltung durch einen [[Aufrufstapel]] realisiert.

{| class="wikitable"
! Iterative Programmierung
! Rekursive Programmierung
|-
| style="vertical-align:top" | <syntaxhighlight lang="python3">
def factorial(number):
    result = 1
    
    while number > 1:
        result *= number
        number -= 1
    
    return result
</syntaxhighlight>
| style="vertical-align:top" | <syntaxhighlight lang="python3">
def factorial(number):
    if number <= 1:
        return 1
    
    return number * factorial(number - 1)
</syntaxhighlight>
|}

Das nächste Beispiel implementiert die [[Fibonacci-Folge]] in der Programmiersprache [[C (Programmiersprache)|C]]. Bei der rekursiven Variante handelt es sich um eine Mehrfachrekursion, die zu einer exponentiellen Laufzeit- und Platzkomplexität führt. Die rekursiven Funktionsaufrufe verzweigen sich zu einem [[Binärbaum]], bei dem identische Teilergebnisse mehrfach berechnet werden. Am häufigsten werden die Fibonaccizahlen an den ersten beiden Stellen berechnet, welche die Abbruchbedingung in der Rekursion definieren. Bei der iterativen Variante ist die Laufzeitkomplexität linear und die Platzkomplexität konstant.

{| class="wikitable"
! Iterative Programmierung
! Rekursive Programmierung
|-
| style="vertical-align:top" | <syntaxhighlight lang="c">
int fibonacci(int number) {
    int first = 0, second = 1;

    for (int count = 0; count < number; ++count) {
        int summand = first;
        first = second;
        second += summand;
    }

    return first;
}
</syntaxhighlight>
| style="vertical-align:top" | <syntaxhighlight lang="c">
int fibonacci(int number) {
    if (number <= 0)
        return 0;

    if (number == 1)
        return 1;

    return fibonacci(number - 1) + fibonacci(number - 2);
}
</syntaxhighlight>
|}

=== Lösen von Rekursionen ===
Beim Lösen einer Rekursion sucht man zum einen den Laufzeitaufwand, zum anderen die explizite Form der Rekursion.

Der Aufwand kann als asymptotische [[Landau-Symbole#Definition|Θ- bzw. Ο-Schranke]] mittels [[Master-Theorem|Mastertheorem]] bzw. [[Substitutionsmethode]] bestimmt werden. Auch das ''geschickte Raten'' mit anschließender [[Vollständige Induktion|Induktion]] bietet eine Möglichkeit, eine [[Landau-Symbole#Definition|obere Schranke]] der Laufzeit zu ermitteln.

Die [[Erzeugende Funktion|explizite Form]] (oder auch geschlossene Form genannt) der Rekursionsgleichung lässt sich beispielsweise durch die erzeugende Funktion finden. Eine zweite Möglichkeit bietet das ''[[Rekursionsableitung|Ableiten]]'' durch Differenzenbildung aufeinanderfolgender Funktionswerte der Rekurrenz.

== Verschiedene Arten des Gebrauchs von Rekursion in verschiedenen und weiteren Wissenschaften  ==
Das Konzept der Rekursion wird in verschiedenen Disziplinen auf unterschiedliche Weise verwendet. Es lassen sich fünf Arten des Gebrauchs unterscheiden: Von der „linear-iterativen“ Rekursion in Mathematik und Informatik und der „generativ-hierarchischen“ Rekursion in Grammatik und Linguistik unterscheiden sich die „organisatorisch-syntaktische“ Rekursion in der Kognitionspsychologie, die „operativ-funktionale“ Rekursion in der Techniktheorie und die „prozessemulative“ Rekursion in der Kulturevolutions- und Zivilisationstheorie.<ref>Zu diesen fünf Typen siehe Davor Löffler: ''Generative Realitäten I. Die Technologische Zivilisation als neue Achsenzeit und Zivilisationsstufe. Eine Anthropologie des 21. Jahrhunderts''. Weilerswist: Velbrück Wissenschaft, 2019, S. 195–204.</ref>

=== Kognitionspsychologie ===
Einen „organisatorisch-syntaktischen“<ref>Vgl. Davor Löffler: ''Generative Realitäten I. Die Technologische Zivilisation als neue Achsenzeit und Zivilisationsstufe. Eine Anthropologie des 21. Jahrhunderts''. Weilerswist: Velbrück Wissenschaft, 2019, S. 197 f.</ref> Begriff der Rekursion arbeitete der [[Evolution des Denkens |evolutionäre Kognitionspsychologe]] [[Michael Corballis]] in seinem Buch ''The Recursive Mind''<ref> Michael C. Corballis, ''The Recursive Mind. The Origins of Human Language, Thought, and Civilization''. Princeton, NJ/Oxford: Princeton University Press, 2013.</ref> aus. Er zeigt, dass die menschliche Fähigkeit zur prinzipiell beliebig tiefen Verschachtelung von Sinn- und Handlungsebenen und zur offenen syntaktischen Aneinanderreihung von Operationseinheiten, wie sie grundsätzlich im Werkzeugverhalten und der Kooperation auftreten, der Sprachfähigkeit vorausgeht und ein allgemeines Merkmal der menschlichen Kognition und Handlungsorganisation ist. So beruhen die beim Menschen stark ausgeprägten Vermögen zu ''mentalen Zeitreisen'' und zur ''[[Theory of Mind]]'' grundsätzlich auf dem Vermögen zur Rekursion.<ref>Vgl. Michael C. Corballis: ''The Recursive Mind. The Origins of Human Language, Thought, and Civilization''. Princeton, NJ/Oxford: Princeton University Press, 2013, S. 82–165.</ref>

=== Techniktheorie ===
Einen „operativ-funktionalen“<ref>Vgl. Davor Löffler: ''Generative Realitäten I. Die Technologische Zivilisation als neue Achsenzeit und Zivilisationsstufe. Eine Anthropologie des 21. Jahrhunderts''. Weilerswist: Velbrück Wissenschaft, 2019, S. 198 f.</ref> Begriff der Rekursion entwickelte der Systemtheoretiker [[W. Brian Arthur]] in seinem Buch ''The Nature of Technology''<ref>W. Brian Arthur: ''The Nature of Technology. What It Is and How It Evolves''. London: Penguin Books, 2009.</ref>. Arthur zeigt, dass alle Technologien eine hierarchische Verschachtelung von Elementen und Funktionsebenen aufweisen, wobei die unteren Elemente ihre operative Funktionalität durch Rekursion zu den oberen Ebenen erhalten, wie er am Beispiel eines Flugzeugträgerverbandes illustriert: Die Turbine eines Kampfjets besteht aus Einzelteilen oder „executables“<ref>Vgl. W. Brian Arthur: ''The Nature of Technology. What It Is and How It Evolves''. London: Penguin Books, 2009, S. 29</ref> wie Schrauben und Luftschaufeln, die rekursiv in die Gesamtfunktion der Turbine eingebettet sind, wie zugleich die Turbine ein rekursiv verschachteltes „executable“ des Kampfjets, der Kampfjet ein „executable“ des Flugzeuträgerverbands und dieser ein „executable“ eines Geschwaders ist.<ref>Vgl. W. Brian Arthur: ''The Nature of Technology. What It Is and How It Evolves''. Penguin Books, London 2009, S.&nbsp;39–44.</ref>

=== Kulturevolutionforschung und Zivilisationstheorie ===
Die gesamte technologische und kulturelle Entwicklung in der [[Evolution des Denkens |Kulturevolution]] und [[Soziokulturelle Evolution|Zivilisationsgeschichte]] weist das Muster der „prozessemulativen“<ref>Vgl. Davor Löffler: ''Generative Realitäten I. Die Technologische Zivilisation als neue Achsenzeit und Zivilisationsstufe. Eine Anthropologie des 21. Jahrhunderts''. Weilerswist: Velbrück Wissenschaft, 2019, S. 199–204.</ref> Rekursion auf, wie der Soziologe Davor Löffler nachgewiesen hat. „Prozessemulative“ Rekursion bezeichnet einen Entwicklungsmechanismus, bei dem ein instrumenteller oder geistiger Vorgang abstrahiert und als materielle oder mediale Emulation wieder eingeführt wird. Dies lässt sich an der frühen Technikevolution nachweisen, in der Entwicklungsstufen jeweils als Grade der Rekursion beschrieben werden können. Dem gegenwärtigen Kenntnisstand nach, zusammengefasst im „Modell der Erweiterung kultureller Kapazitäten“<ref>Miriam N. Haidle, Michael Bolus, Mark Collard et al.: ''The Nature of Culture: An Eight-Grade Model for the Evolution and Expansion of Cultural Capacities in Hominins and other Animals''. In: ''Journal of Anthropological Sciences'', Jg. 93, 2015, S. 43–70.</ref>, folgen entwicklungsgeschichtlich auf einfache [[Steingerät |Steinwerkzeuge]] („Modularkultur“<ref>Vgl. Miriam N. Haidle, Michael Bolus, Mark Collard et al.: ''The Nature of Culture: An Eight-Grade Model for the Evolution and Expansion of Cultural Capacities in Hominins and other Animals''. In: ''Journal of Anthropological Sciences'', Jg. 93, 2015, S. 56 f.</ref>, >2,6 [[Jahrmillion|Ma]]) Kompositwerkzeuge wie Hammersteine mit Griff oder Speere mit Knochenspitzen („Kompositkultur“<ref>Vgl. Miriam N. Haidle, Michael Bolus, Mark Collard et al.: ''The Nature of Culture: An Eight-Grade Model for the Evolution and Expansion of Cultural Capacities in Hominins and other Animals''. In: ''Journal of Anthropological Sciences'', Jg. 93, 2015, S. 57 f.</ref>, >500 [[Jahrtausend|ka]]), hierauf aus komplementären, voneinander unabhängigen Modulen zusammengesetzte Apparate wie Pfeil-und-Bogen oder Nadel und Faden („Komplementärkultur“<ref>Miriam N. Haidle, Michael Bolus, Mark Collard et al.: ''The Nature of Culture: An Eight-Grade Model for the Evolution and Expansion of Cultural Capacities in Hominins and other Animals''. In: ''Journal of Anthropological Sciences'', Jg. 93, 2015, S. 58.</ref>, >70 [[Jahrtausend|ka]]), hierauf ideelle Werkzeuge wie Höhlenmalereien, Musikinstrumente oder Fallen („ideelle Kultur“<ref>Miriam N. Haidle, Michael Bolus, Mark Collard et al.: ''The Nature of Culture: An Eight-Grade Model for the Evolution and Expansion of Cultural Capacities in Hominins and other Animals''. In: ''Journal of Anthropological Sciences'', Jg. 93, 2015, S. 58–60.</ref>, >40 [[Jahrtausend|ka]]). Die Technologiestrukturen der kumulativ aufeinander aufbauenden Entwicklungsstufen gründen jeweils auf der „prozessemulativen“ Rekursion der Vorgänge der vorherigen Stufen. Beispielsweise emuliert der Apparat des Pfeil-und-Bogens („Komplementärkultur“) rekursiv den Vorgang des Speerwurfs („Kompositkultur“), und die Falle („ideelle Kultur“) emuliert rekursiv die Anwesenheit einer Jägergruppe bzw. der Fallenmechanismus den Auslösemechanismus des Bogens („Komplementärkultur“). Die „prozessemulative“ Rekursion durchzieht als allgemeines Prinzip die gesamte Technikgeschichte: So beruht beispielsweise der Mikrowellenherd auf der „prozessemulativen“ Rekursion, da darin der Vorgang der Erhitzung von Nahrung etwa durch einen Ofen emuliert wird; die digitale Mustererkennung beruht auf der prozessemulativen Rekursion menschlicher Mustererkennung usw. Es wurde gezeigt, dass das Entwicklungsprinzip der „prozessemulativen“ Rekursion auch den Entwicklungen der gesamten Zivilisationsgeschichte zugrunde liegt und neben der Technologie auch in anderen Bereichen auftritt, etwa der Ökonomie, den Medien, der Politik, der Entwicklung von Kognitionsstrukturen, der Kunst und der Mathematik, wobei wiederum jede Entwicklungsstufe dieser Bereiche auf der rekursiven Emulation der Vorgänge der vorherigen Entwicklungsstufe beruht.<ref>Eine zusammenfassende Tabelle findet sich in Davor Löffler: ''Generative Realitäten I. Die Technologische Zivilisation als neue Achsenzeit und Zivilisationsstufe. Eine Anthropologie des 21. Jahrhunderts''. Weilerswist: Velbrück Wissenschaft, 2019, S. 600 f.</ref> So lassen sich kumulativ aufeinander folgende Entwicklungsphasen der Zivilisationsgeschichte ([[Hochkultur (Geschichtswissenschaft) |frühe Hochkulturen]], [[Achsenzeit]] und [[Neuzeit]]) als Ausdruck von „prozessemulativen“ Rekursionen erklären.<ref>Vgl. Davor Löffler: ''Generative Realitäten I. Die Technologische Zivilisation als neue Achsenzeit und Zivilisationsstufe. Eine Anthropologie des 21. Jahrhunderts''. Velbrück Wissenschaft, Weilerswist 2019, S. 621–640.</ref>

== Siehe auch ==
<!-- Hier keinen Link auf diesen Artikel einfügen. Wir kennen den Witz alle, doch die Wikipedia ist keine Witzesammlung. …für alle die den Witz nicht verstanden haben: Dies wäre eine Rekursion. -->

* [[Backtracking]]
* [[Fixpunkt (Mathematik)]]
* [[Kellerautomat]]
* [[Logo (Programmiersprache)]]
* [[Rekursionssatz]]
* [[Rekursive Sprache]]
* [[Rekursives Akronym]]
* [[Selbstähnlichkeit]]
* [[Türme von Hanoi]] – typische Anwendung von Rekursion
* [[µ-Rekursion]] <!-- sollte im Artikel erwähnt werden! -->

== Literatur ==
* Niklaus Wirth: ''Algorithmen und Datenstrukturen''. 5. Auflage. B.G. Teubner, Stuttgart 2000. (1. Auflage: 1975). ISBN 978-3-519-22250-7, [[doi:10.1007/978-3-322-80154-8]].

== Weblinks ==
{{Wiktionary}}
{{Wiktionary|rekursiv}}
{{Wikibooks|Rekursive Labyrinthe}}

== Einzelnachweise ==
<references />

{{Normdaten|TYP=s|GND=4191814-9}}

[[Kategorie:Rekursion| ]]