Rekursion ist ein allgemeines Prinzip zur Lösung von Problemen, das in vielen Fällen zu "eleganten" mathematischen Lösungen führt. Als Rekursion bezeichnet man den Aufruf bzw. die Definition einer Funktion durch sich selbst. Ohne geeignete Abbruchbedingung geraten solche rückbezüglichen Aufrufe in einen sog. infiniten Regress.
(Hinweis vorab: Rekursion oder rekursive Definitionen sind nicht auf natürliche Zahlen-definierte Funktionen beschränkt. Hier sei auf das verallgemeinerte Rekursionsschema verwiesen.)
Die Grundidee der rekursiven Definition einer Funktion f ist: Der Funktionswert f(n+1) einer Funktion f: N0 → N0 ergibt sich durch Verknüpfung bereits vorher berechneter Werte f(n), f(n-1),... Falls außerdem die Funktionswerte von f für hinreichend viele Startargumente bekannt sind, kann jeder Funktionswert von f berechnet werden. Das heißt im Klartext: Bei einer rekursiven Definition einer Funktion f ruft sich die Funktion so oft selber auf, bis ein vorgegebenes Argument (meistens 0) erreicht ist, so dass die Funktion terminiert (sich unterbricht).
Die Definition von rekursiv festgelegten Funktionen ist eine grundsätzliche Vorgehensweise in der funktionalen Programmierung. Ausgehend von einigen gegebenen Funktionen (wie zum unten die Summen-Funktion) werden neue Funktionen definiert, mithilfe derer weitere Funktionen definiert werden können.
Hier ein Beispiel für eine Funktion sum: N0 → N0, die die Summe der ersten n Zahlen berechnet:
Die Funktion sum sei definiert durch: sum(n) = 0 + 1 + 2 +...+ n
oder besser: sum(n) = sum(n-1) + n (Rekursionsschritt)
Das heißt also, die Summe der ersten n Zahlen lässt sich berechnen, indem man die Summe der ersten n - 1 Zahlen berechnet und dazu die Zahl n addiert. Damit die Funktion terminiert legt man hier für sum(0) = 0 (Rekursionsanfang) fest. Mit diesen Angaben lässt sich eine rekursive Definition angeben, die eine beliebige (hier: natürliche) Zahl x berechnet. Die Definition lautet also:
| sum(n) = { | 0, falls n = 0 (Rekursionsanfang) |
| sum(n-1) + n, falls n ≥ 1 (Rekursionsschritt) |
Es gilt nun zum Beispiel:
| sum(3) = | sum(2) + 3 (Rekursionsschritt) |
| = | sum(1) + 2 + 3 (Rekursionsschritt) |
| = | sum(0) 1 + 2 + 3 (Rekursionsschritt) |
| = | 0 + 1 + 2 + 3 (Rekursionsanfang) |
| = | 6 |
Ein Spezialfall der Rekursion ist die Iteration. Diese tritt auf, wenn der rekursive Funktionsaufruf nur am Anfang oder nur am Ende innerhalb der Funktion benutzt wird (siehe Endrekursion).
Rekursion: siehe Rekursion