Rekursion

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: N₀ → N₀ 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: N₀ → N₀, 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