Rekursion

Rekursion bedeutet Selbstbezüglichkeit. Sie tritt immer dann auf, wenn etwas auf sich selbst verweist. Ein rekursives Element muss nicht direkt auf sich selbst verweisen, eine Rekursion kann auch über mehrere Zwischenschritte entstehen. Rekursion kann dazu führen, dass merkwürdige Schleifen entstehen. So ist z.B. der Satz "Dieser Satz ist unwahr" rekursiv, da er von sich selber spricht. Eine etwas subtilere Form der Rekursion kann auftreten, wenn zwei Dinge gegenseitig aufeinander verweisen. Ein Beispiel sind die beiden Sätze: "Der folgende Satz ist wahr" "Der vorhergehende Satz ist nicht wahr". Die Probleme beim Verständnis von Rekursion beschreibt der Satz: "Um Rekursion zu verstehen, muss man erst einmal Rekursion verstehen".

Rekursion ist ein allgemeines Prinzip zur Lösung von Problemen. In vielen Fällen ist die Rekursion eine von mehreren möglichen Problemlösungsstrategien, sie führt oft zu "eleganten" mathematischen Lösungen führt. Als Rekursion bezeichnet man den Aufruf oder die Definition einer Funktion durch sich selbst. Ohne geeignete Abbruchbedingung geraten solche rückbezüglichen Aufrufe in einen so genannten 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: N₀ → N₀ 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: 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 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:

${\mbox{sum}}(n)=\left\{{\begin{matrix}0&&{\mbox{falls }}n=0&&{\mbox{(Rekursionsanfang)}}\\{\mbox{sum}}(n-1)+n&&{\mbox{falls }}n\geq 1&&{\mbox{(Rekursionsschritt)}}\end{matrix}}\right.$

Es gilt nun zum Beispiel:

${\begin{matrix}{\mbox{sum}}(3)&=&{\mbox{sum}}(2)+3&{\mbox{(Rekursionsschritt)}}\\&=&{\mbox{sum}}(1)+2+3&{\mbox{(Rekursionsschritt)}}\\&=&{\mbox{sum}}(0)+1+2+3&{\mbox{(Rekursionsschritt)}}\\&=&0+1+2+3&{\mbox{(Rekursionsschritt)}}\\&=&6\end{matrix}}$

Ein Spezialfall der Rekursion ist die Iteration. Eine Iteration tritt auf, eine Funktion sich selbst nur am Anfang oder nur am Ende (Endrekursion) innerhalb der Funktion aufruft.

In der Theoretischen Informatik spielen primitiv-rekursive Funktionen eine wichtige Rolle. Im Compilerbau ist der rekursive Abstieg eine Technik, bei der eine Computersprache rekursiv geparst wird.