Rekursion ist ein allgemeines Problemlöseprinzip, welches 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.
(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 ausserdem die Funktionswerte von f für hinreichend viele Startargumente bekannt sind, kann jeder Funktionswert von f berechnet werden. Das heisst 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).
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 heisst 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 |