Das Wort rekursiv dürfte von lateinisch recurrere "zurücklaufen" stammen. Es wird allgemein in der Bedeutung "mit Rückbezug auf sich selbst" verwendet. Genauer nennt man in der Informatik solche Strukturen rekursiv, in denen ein Teil der Struktur dem ganzen strukturell gleich ist.

Eine Datenstruktur heißt rekursiv, wenn ein oder mehrere Bestandteile der Datenstruktur dieselbe Struktur besitzt wie die gesamte Datenstruktur selbst. Bäume sind rekursive Datenstrukturen, siehe nächstes Kapitel.

Ein Algorithmus (eine Funktion) heißt rekursiv, wenn er zur Lösung eines Teilproblems denselben Algorithmus - sich selbst - anwendet. Ein einfaches Beispiel für einen rekursiven Algorithmus ist die Berechnung der Fibonacci-Zahlen: Per Definition gilt:

• f(0) = 0
• f(1) = 1 und
• f(x) = f(x-1) + f(x-2), falls x > 1

Die Berechnung der vierten Fibonacci-Zahl ergibt sich also wie folgt:

f(4) = f(3) + f(2) = f(2) + f(1) + f(1) + f(0) = f(1) + f(0) + f(1) + f(1) + f(0) = 1 + 0 + 1 + 1 + 0 = 3.

Rekursive Algorithmen lassen i.d.R auch immer iterativ (mit Schleifen) ausdrücken. Bestimmte Probleme allerdings, wie z.B. das klassische Problem der Berechung von n! lassen sich am besten rekursiv formulieren. Indess lassen sich nicht alle iterativ formulierbare Algorithmen rekursiv ausdrücken.

Beispiel des rekursiv formulierten binären Suchens

Die Grundidee kann man so formulieren:

Binäres Suchen auf dem Teilintervall left, right des Array a nach dem Suchwert x:

• Berechne mid als (left+right)/2 und vergleiche amid mit dem Suchwert x.
• Ist der Wert noch nicht gefunden, so schränke das Suchintervall maximal ein auf newLeft und newRight und wende,
• wenn newLeft <= newRight, den Algorithmus erneut auf das neue, kleinere Teilintervall an:

Als rekursive Funktion (Methode) in Java formuliert, sieht das so aus:

Die Funktion recursiveBinarySearch ruft sich dabei selbst auf, mit geänderten Parameterwerten, sooft, bis der Wert gefunden worden ist oder das Suchintervall leer geworden ist. Man beachte die if-Abfrage, die die Rekursion beendet! Sie entspricht der Schleifenkontrollabfrage der do-while-Schleife einer iterativen Lösung.

Betrachten wir nun zur Vorbereitung auf die nähere Betrachtung des Ablaufs einer Kette rekursiver Aufrufe zunächst eine Kette nichtrekursiver Funktionsaufrufe, unten bei func1 beginnend:

 

An einem bestimmten Punkt innerhalb der Ausführung von func1 wird in die Ausführung von func2 "gesprungen". Die weitere Ausführung von func1 bleibt ausgesetzt, bis die Ausführung von func2 beendet ist und deren Ergebnis zurückgegeben wurde. Danach wird die Ausführung von func1 an der richtigen Stelle fortgesetzt. func2 seinerseits ruft func3 auf. Im Moment der Ausführung von func3 befinden sich also func1, func2 und func3 in verschiedenen Stadien ihrer Ausführung. Das Runtime-System verwaltet diese Kette (Stapel) von Aufrufen in einem sogenannten call stack, wozu im wesentlichen die Speicherung der Rücksprungsadressen reicht. Der Stapel verlängert sich beim Aufruf einer Funktion und verkürzt sich beim Rücksprung.

Beim binären Suchen wird ein und dieselbe Funktion (unten doSearch genannt) mehrfach aufgerufen. Ihr Code braucht dazu aber nicht mehrfach im Speicher vorhanden zu sein. Es reicht, je Funktionsaufruf die Parameter, die lokalen Variablen und die Rücksprungadresse verfügbar zu haben. Diese Informationen werden als 'activation records' oder 'stack frames' auf dem call stack verwaltet, siehe Grafik unten. Lesen Sie die Grafik bitte von unten nach oben.

 

search(v, s) sucht in einem Vector oder Array von Strings nach "Dora". Es wird die rekursive binäre Suche mit doSearch aufgerufen. Das Laufzeitsystem des Programms legt für jeden Aufruf die Parameter, die Rücksprungadresse und die lokalen Variablen (compres, mid) auf den intern verwalteten Aufrufstack. FORTRAN ist ein Klassiker unter den Programmiersprachen, der nach wie vor keine Rekursion anbietet. In FORTAN muß man also rekursive Algorithmen iterativ formulieren.