Infos Home | Impressum | Original Artikel & Autoren Liste

Rekursion

Rekursion bedeutet Selbstbezüglichkeit (von lateinisch recurrere = zurücklaufen). 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. 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.

Zur Vermeidung von infinitem Regress insbesondere in Computerprogrammen bedient man sich der semantischen Verifikation von rekursiven Funktionen. Der Beweis, dass kein infiniter Regress vorliegt, wird dann zumeist mittels eine Schleifeninvariante geführt (siehe auch Invariante). Dieser Beweis ist allerdings nicht immer möglich (siehe Halteproblem).

Inhalt
1 Definition
2 Beispiel
3 Programmierbeispiel
4 Bedeutung

Definition

(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 z.B. die Summen-Funktion) werden neue Funktionen definiert, mithilfe derer weitere Funktionen definiert werden können.

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

Beispiel

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:

Es gilt nun zum Beispiel:

Programmierbeispiel

Die beliebte und einfache Implementierung der Fakultätsberechnung. Hier als rekursive Variante und unter Umgehung von Rekursion.

public class Faculty {
public static void main(String[] args) {
	try { System.out.println(args[0]+"! = " + facultyRec(Integer.parseInt(args[0])));}
	catch (Throwable t) {System.err.println("Ungültiger Parameter !");}
}

/** Rekursive Methode zur Fakultätsberechnung */
public static long facultyRec(int n) {
	return n==0?1:n*facultyRec(Math.abs(n)-1); 
}

/** Nicht-rekursive Methode zur Fakultätsberechnung */
public static long facultyNonRec(int n) {
	int i = 1;
	while (Math.abs(n)>0) {
		i *= n;
		n = Math.abs(n) - 1;
	} 
	return i;
}
}

Die Entscheidung, ob man Rekursion in der Programmierung einsetzt oder nicht, hängt von der Performanz und dem Speicherverbrauch ab. Somit ist die Rekursion nicht immer die bessere Wahl.

Bedeutung

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.


Der Ursprungsartikel stammt von der deutschsprachigen Wiki pedia (siehe oben: "Original Artikel & Autoren Liste").
Der Text steht unter der GNU Freie Dokumentation Lizenz.