Rekursion

Aus AnthroWiki
(Weitergeleitet von Rekursiv)
Unendlichfache Spiegelung als Beispiel für Rekursion: Die Person sitzt mit vorgehaltenem Spiegel einem größeren Wandspiegel gegenüber. Das jeweils folgende Spiegelbild enthält sich selbst als Teil.

Als Rekursion (lat. recurrere, deutsch ‚zurücklaufen‘) bezeichnet man den abstrakten Vorgang, dass Regeln auf ein Produkt, das sie selbst erzeugt haben, von neuem angewandt werden. Hierdurch entstehen potenziell unendliche Schleifen. Regeln bzw. Regelsysteme heißen rekursiv, wenn sie die Eigenschaft haben, Rekursion im Prinzip zuzulassen.

Allgemeines

Rekursion ist ein zentraler Begriff in Mathematik und Informatik und hat vielfältige Anwendungen darüber hinaus; diese reichen bis in die Kunst, wo das Phänomen auch als mise en abyme bezeichnet worden ist.

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. Beispielsweise ist die rekursive Programmierung Bestandteil vieler Programmiersprachen. Prozeduren oder Funktionen können sich dabei selbst aufrufen. Rekursion und Iteration sind im Wesentlichen gleichmächtige Sprachmittel.

In Mathematik und Informatik erscheint Rekursion auch spezieller in der Form, dass eine Funktion in ihrer Definition selbst nochmals aufgerufen wird (rekursive Definition). Wenn man mehrere Funktionen durch wechselseitige Verwendung voneinander definiert, spricht man von wechselseitiger Rekursion. Nicht jede rekursive Definition ist eine Definition im eigentlichen Sinn, denn die zu definierende Funktion braucht nicht wohldefiniert zu sein. Jeder Aufruf der rekursiven Funktion muss sich durch Entfalten der rekursiven Definition in endlich vielen Schritten auflösen lassen. Ist dies nicht erfüllt, so spricht man von einem infiniten Regress (in der Informatik auch als Endlosschleife bezeichnet).

Zum Thema einführende Beispiele für Rekursion siehe auch

Rekursive Definition einer Funktion und Untertypen von Rekursion

Mathematische Definition

(Hinweis vorab: Rekursionsverfahren und rekursive Definitionen sind nicht auf Funktionen natürlicher Zahlen beschränkt. Hier sei auf das verallgemeinerte Rekursionsschema verwiesen.)

Das Grundprinzip der rekursiven Definition einer Funktion f ist: Der Funktionswert f(n+1) einer Funktion f : N0N0 ergibt sich durch 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).

Die Definition von rekursiv festgelegten Funktionen ist eine grundsätzliche Vorgehensweise in der funktionalen Programmierung. Ausgehend von einigen gegebenen Funktionen (wie z. B. der Summenfunktion) werden neue Funktionen definiert. Mit diesen können weitere Funktionen definiert werden.

Ein Spezialfall der Rekursion ist die primitive Rekursion, die stets durch eine Iteration ersetzt werden kann. Bei einer solchen Rekursion enthält der Aufrufbaum keine Verzweigungen, das heißt, er ist eine Aufrufkette: das ist immer dann der Fall, wenn eine rekursive Funktion sich selbst jeweils nur einmal aufruft. Der Aufruf kann dabei am Anfang (Head Recursion, siehe Infiniter Regress) oder am Ende (Tail Recursion oder Endrekursion) der Funktion erfolgen. Umgekehrt kann jede Iteration durch eine primitive Rekursion ersetzt werden, ohne dass sich dabei die Komplexität des Algorithmus ändert.

Formen der 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.

Die primitive Rekursion ist ein Spezialfall der linearen Rekursion. 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 Stapels durch eine Schleife (Programmierung) (z. 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 unmittelbar durch While-Schleifen ersetzen und umgekehrt.

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.

Verwendung des Konzepts Rekursion in 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.[1]

Kognitionspsychologie

Einen „organisatorisch-syntaktischen“[2] Begriff der Rekursion arbeitete der evolutionäre Kognitionspsychologe Michael Corballis in seinem Buch The Recursive Mind[3] 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.[4]

Techniktheorie

Einen „operativ-funktionalen“[5] Begriff der Rekursion entwickelte der Systhemtheoretiker W. Brian Arthur in seinem Buch The Nature of Technology[6]. 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“[7] 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.[8]

Kulturevolutionforschung und Zivilisationstheorie

Die gesamte technologische und kulturelle Entwicklung in der Kulturevolution und Zivilisationsgeschichte weist das Muster der „prozessemulativen“[9] 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“[10], folgen entwicklungsgeschichtlich auf einfache Steinwerkzeuge („Modularkultur“[11], >2.6 Ma) Kompositwerkzeuge wie Hammersteine mit Griff oder Speere mit Knochenspitzen („Kompositkultur“[12], >500 ka), hierauf aus komplementären, voneinander unabhängigen Modulen zusammengesetzte Apparate wie Pfeil-und-Bogen oder Nadel und Faden („Komplementärkultur“[13], >70 ka), hierauf ideelle Werkzeuge wie Höhlenmalereien, Musikinstrumente oder Fallen („ideelle Kultur“[14], >40 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.[15] So lassen sich kumulativ aufeinander folgende Entwicklungsphasen der Zivilisationsgeschichte (frühe Hochkulturen, Achsenzeit und Neuzeit) als Ausdruck von „prozessemulativen“ Rekursionen erklären.[16]

Siehe auch

Weblinks

 Wiktionary: Rekursion – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen
 Wiktionary: rekursiv – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

Einzelnachweise

  1. 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.
  2. 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.
  3. Michael C. Corballis, The Recursive Mind. The Origins of Human Language, Thought, and Civilization. Princeton, NJ/Oxford: Princeton University Press, 2013.
  4. 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.
  5. 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.
  6. W. Brian Arthur: The Nature of Technology. What It Is and How It Evolves. London: Penguin Books, 2009.
  7. Vgl. W. Brian Arthur: The Nature of Technology. What It Is and How It Evolves. London: Penguin Books, 2009, S. 29
  8. Vgl. W. Brian Arthur: The Nature of Technology. What It Is and How It Evolves. London: Penguin Books, 2009, S. 39–44
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. 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.
  14. 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.
  15. 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.
  16. 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. 621–640.
Dieser Artikel basiert (teilweise) auf dem Artikel Rekursion aus der freien Enzyklopädie Wikipedia und steht unter der Lizenz Creative Commons Attribution/Share Alike. In Wikipedia ist eine Liste der Autoren verfügbar.