Rekursion

Als Rekursion (lateinisch recurrere ‚zurücklaufen‘) wird ein prinzipiell unendlicher Vorgang, der sich selbst als Teil enthält oder mithilfe von sich selbst definierbar ist, bezeichnet.^[1] Üblicherweise sind rekursive Vorgänge relativ kurz beschreibbar bzw. können durch eine relativ kurze Anweisung ausgelöst werden.^[2][3] 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“.^[4] In der Natur handelt es sich um einen häufig beobachtbaren Vorgang (z. B. beim Pflanzenwachstum oder Blüten). In vielen Bereichen der Kultur wird er nachgebildet, so in den schönen Künsten, wo das Phänomen u. 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. a. auch beim sogenannten rekursiven Programmieren genutzt: Um Rekursion entstehen zu lassen, muss eine Prozedur, Funktion oder Methode lediglich sich selbst aufrufen. Dieser Prozess läuft weiter, bis eine im Programm enthaltene Abbruchbedingung greift.

In der Mathematik wird das rekursive Formulieren mit Vorteil zur Erklärung von Funktionen angewendet (siehe Rekursive Definition).

1. ↑ Niklaus Wirth, Seite 149: 3. Rekursion, 3.1. Einleitung
2. ↑ 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.“
3. ↑ Referenzfehler: Ungültiges <ref>-Tag; kein Text angegeben für Einzelnachweis mit dem Namen Buss.
4. ↑ Douglas R. Hofstadter: Gödel, Escher, Bach. dtv, 2004, Seite 137.