Rekursion

Grundidee und Bedeutung

Rekursion ist ein prinzipiell unendlicher Vorgang, der sich selbst als Teil enthält oder mithilfe von sich selbst definierbar ist. Die einzelnen Schritte oder erzeugten Objekte sind dabei nicht unabhängig: Zwischen jeweils zwei Schritten beziehungsweise Objekten besteht eine besondere rekursive Beziehung. Rekursive Vorgänge lassen sich oft durch kurze Regeln oder Anweisungen beschreiben.

Rekursion kommt in der Natur, etwa beim Pflanzenwachstum oder bei Blüten, sowie in Kultur, Kunst, Mathematik und Informatik vor. Sie ist außerdem eine Problemlösungsstrategie: Eine allgemeine, komplexe Aufgabe wird auf eine einfachere Aufgabe derselben Klasse zurückgeführt. In einem Programm ruft dazu eine Prozedur, Funktion oder Methode sich selbst auf. Die Wiederholung muss durch eine Abbruchbedingung enden. In der Mathematik dient Rekursion besonders zur Definition von Funktionen.

Rekursive Strukturen in Grafik und Sprache

Rekursive Regeln können Fraktale erzeugen, also ästhetisch ansprechende und natürlich wirkende Gebilde. Beim Pythagoras-Baum wird auf einer Grundlinie ein Quadrat errichtet, auf dessen Oberseite ein Dreieck mit vorgegebenen Winkeln oder einer vorgegebenen Höhe gezeichnet wird. Dieselben Schritte werden dann auf die beiden freien Seiten des neuen Dreiecks angewandt. Der Algorithmus wird bis zu einer vorgegebenen Rekursionstiefe entfaltet. Mit wachsender Tiefe ähnelt das Gebilde immer stärker einem Baum.

In der Linguistik werden Grammatiken natürlicher Sprachen unter anderem durch Phrasenstrukturregeln beschrieben. Nach Ansicht der meisten Linguisten sind alle menschlichen Sprachen rekursiv aufgebaut, anders als Signalsysteme im Tierreich. Rekursion liegt vor, wenn bei der Zerlegung einer grammatischen Einheit dieselbe Kategorie erneut erscheint. Eine stark vereinfachte Beschreibung von Nebensätzen lautet: S → NP VP; VP → V NP*; VP → V S. Dabei steht S für Satz, NP für Nominalphrase und VP für Verbalphrase. Über VP → V S erscheint wieder ein S, das erneut mit S → NP VP weiter zerlegt werden kann. Auch über NP kann Rekursion entstehen.

Rekursive Funktionen in der Mathematik

In der Mathematik werden Funktionen häufig rekursiv definiert. Verwandt mit diesem Vorgehen sind der Nachfolger in den Peano-Axiomen und die vollständige Induktion. Rekursionsverfahren und rekursive Definitionen sind nicht auf Funktionen natürlicher Zahlen beschränkt.

Die Fakultät einer natürlichen Zahl n ≥ 1 ist das Produkt aller Zahlen von 1 bis n: n! = 1 · 2 · 3 … n = ∏(k=1 bis n) k. Beispielsweise gilt 1! = 1, 2! = 2, 3! = 6 und 4! = 24. Rekursiv lautet die Definition: n! = 1, falls n = 1 (Rekursionsanfang); andernfalls n! = (n−1)! · n (Rekursionsschritt). Daher ist 5! = 4! · 5 = 120.

Bei der Fibonacci-Folge ist jedes Folgenglied die Summe der zwei vorhergehenden: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … . Laut Artikel ist dafür keine kompakte geschlossene Form definiert; die einfachste Beschreibung ist rekursiv: fib(0) = 0, fib(1) = 1 und fib(n) = fib(n−1) + fib(n−2) für die übrigen Fälle. Diese Rekursion ist kaskadenförmig: Bei fib(3) werden fib(2) und fib(1) benötigt, für fib(2) wiederum fib(1) und fib(0). Das Ergebnis ist fib(3) = 2. Dabei wird fib(1) mehrfach berechnet; dies weist auf Optimierungsmöglichkeiten hin.

Formale Rekursionsarten

Bei linearer Rekursion enthält jeder Fall der rekursiven Definition höchstens einen rekursiven Aufruf. Die Berechnung bildet eine Kette, der Aufrufbaum verzweigt sich nicht.

Primitive Rekursion ist ein Sonderfall der linearen Rekursion für Funktionen auf natürlichen Zahlen. Im rekursiven Aufruf wird der erste Parameter jeweils um Eins erhöht oder vermindert. Jede primitiv-rekursive Definition kann mithilfe eines Stapels durch eine Schleife, etwa eine For- oder While-Schleife, ersetzt werden.

Endständige oder repetitive Rekursion (Tail Recursion, Endrekursion) liegt vor, wenn der rekursive Aufruf die letzte Aktion eines Aufrufs ist. Sie kann durch eine While-Schleife ersetzt werden und umgekehrt. Bei verschachtelter Rekursion stehen rekursive Aufrufe in Parameterausdrücken anderer rekursiver Aufrufe; diese Form gilt als besonders schwer zu durchschauen. Kaskadenförmige Rekursion enthält mehrere nebeneinanderstehende rekursive Aufrufe und bildet daher einen Baum. Sie kann ohne zusätzliche Maßnahmen exponentiellen Berechnungsaufwand verursachen. Wechselseitige Rekursion definiert mehrere Funktionen durch ihre gegenseitige Verwendung und lässt sich auf die gewöhnliche Rekursion einer tupelwertigen Funktion zurückführen.

Rekursion und Iteration in Programmen

Höhere Programmiersprachen, die mit Funktionen arbeiten, erlauben meist Rekursion; viele Aufgaben lassen sich sowohl rekursiv als auch iterativ lösen. Bei Iteration wird eine Schleife wie for oder while wiederholt, bis eine Abbruchbedingung erfüllt ist. Bei Rekursion ruft eine Funktion oder Prozedur sich mit regelmäßig verändertem Parameter erneut auf, ebenfalls bis zur Abbruchbedingung.

Rekursion benötigt in der Regel weniger Quellcode und kann für erfahrene Anwender übersichtlicher sein, weil Hilfsvariablen und Schleifenzähler entfallen. Iterative Verfahren sind bei der Ausführung meist effizienter und speichersparender. Rekursive Funktionsaufrufe samt Zwischenergebnissen werden auf dem Stapelspeicher (Stack) abgelegt; dadurch kann ein Stack Overflow entstehen. Bei Echtzeitsystemen auf Mikrocontrollern wird deshalb häufig auf Rekursion verzichtet. Manche funktionalen Programmiersprachen erlauben keine Iteration und setzen primitive Rekursionen intern als Iterationen um.

Bei der Fakultät haben iterative und rekursive Implementierungen lineare Laufzeit in Abhängigkeit vom Eingabewert. Die iterative Variante benötigt konstanten Speicher, die rekursive linearen Speicher. Eine naive rekursive Fibonacci-Implementierung ist Mehrfachrekursion: Ihre Aufrufe bilden einen Binärbaum, berechnen gleiche Teilergebnisse wiederholt und haben exponentielle Laufzeit- und Platzkomplexität. Die iterative Variante hat lineare Laufzeit und konstante Platzkomplexität. Memoisation vermeidet die Mehrfachberechnung durch Wiederverwendung gespeicherter Zwischenlösungen. Rekursion ist wichtig für Teile-und-herrsche-Strategien (Divide and Conquer); Greedy-Algorithmen verlangen dagegen iteratives Vorgehen. Weitere Rollen hat sie in Komplexitäts- und Berechenbarkeitstheorie sowie beim rekursiven Abstieg im Compilerbau, einer Technik zum rekursiven Parsen von Sprachen.

Zum Lösen einer Rekursion bestimmt man entweder den Laufzeitaufwand oder eine explizite, geschlossene Form. Asymptotische Θ- oder O-Schranken lassen sich mit Mastertheorem, Substitutionsmethode oder Raten mit anschließender Induktion ermitteln. Geschlossene Formen können etwa über erzeugende Funktionen oder durch Differenzenbildung aufeinanderfolgender Funktionswerte einer Rekurrenz gefunden werden.

Rekursion in weiteren Wissenschaften

Der Artikel unterscheidet fünf Gebrauchsarten: „linear-iterative“ Rekursion in Mathematik und Informatik, „generativ-hierarchische“ Rekursion in Grammatik und Linguistik, „organisatorisch-syntaktische“ Rekursion in der Kognitionspsychologie, „operativ-funktionale“ Rekursion in der Techniktheorie und „prozessemulative“ Rekursion in Kulturevolutions- und Zivilisationstheorie.

Michael Corballis beschreibt Rekursion als Fähigkeit, Sinn- und Handlungsebenen grundsätzlich beliebig tief zu verschachteln und Operationseinheiten offen aneinanderzureihen. Diese Fähigkeit zeige sich im Werkzeugverhalten und in Kooperation, gehe der Sprachfähigkeit voraus und sei ein allgemeines Merkmal menschlicher Kognition und Handlungsorganisation. Auch mentale Zeitreisen und Theory of Mind beruhen demnach grundsätzlich auf Rekursion.

W. Brian Arthur beschreibt Technologien als hierarchisch verschachtelte Elemente und Funktionsebenen. Untere Elemente erhalten ihre operative Funktion durch ihre Einbettung in obere Ebenen. Beim Flugzeugträgerverband sind etwa Schrauben und Luftschaufeln Bestandteile der Turbine eines Kampfjets; die Turbine ist Teil des Kampfjets, der Kampfjet Teil des Verbands und dieser Teil eines Geschwaders.

Davor Löffler bezeichnet als „prozessemulative“ Rekursion einen Entwicklungsmechanismus, bei dem ein instrumenteller oder geistiger Vorgang abstrahiert und als materielle oder mediale Emulation wieder eingeführt wird. Das Modell der Erweiterung kultureller Kapazitäten nennt aufeinander folgende Stufen: Modularkultur mit einfachen Steinwerkzeugen (>2,6 Ma), Kompositkultur mit Kompositwerkzeugen (>500 ka), Komplementärkultur mit Apparaten aus unabhängigen Modulen (>70 ka) und ideelle Kultur mit ideellen Werkzeugen (>40 ka). Pfeil und Bogen emulieren dabei rekursiv den Speerwurf, eine Falle die Anwesenheit einer Jägergruppe beziehungsweise der Fallenmechanismus den Auslösemechanismus des Bogens. Das Prinzip wird laut Artikel auch auf Technikgeschichte und weitere Bereiche der Zivilisationsgeschichte wie Ökonomie, Medien, Politik, Kognition, Kunst und Mathematik bezogen.