Rekursion, auch Rekurrenz oder Rekursivität, bedeutet Selbstbezüglichkeit (von lateinisch recurrere = zurücklaufen). Sie tritt immer dann auf, wenn etwas auf sich selbst verweist. Ein rekursives Element muss nicht immer direkt auf sich selbst verweisen (direkte Rekursion), 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 (indirekte 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 (umgangssprachlich Endlosschleife).
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 einer Schleifeninvariante geführt (siehe auch Invariante). Dieser Beweis ist allerdings nicht immer möglich (siehe Halteproblem).
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, mit Hilfe derer weitere Funktionen definiert werden können.
Ein Spezialfall der Rekursion ist die primitive Rekursion, die stets durch eine Iteration ersetzt werden kann. Bei einer solchen Rekursion enthält der Aufruf-Baum keine Verzweigungen, das heißt er ist eigentlich eine Aufruf-Kette: das ist immer dann der Fall, wenn eine rekursive Funktion sich selbst jeweils nur einmal aufruft, insbesondere am Anfang (Head Recursion, siehe Infiniter Regress) oder nur am Ende (Tail Recursion oder Endrekursion) der Funktion. Umgekehrt kann jede Iteration durch eine primitive Rekursion ersetzt werden, ohne dass sich dabei die Komplexität des Algorithmus ändert.
Anwendung
Im Fall von primitiv-rekursiven Funktionen steht es dem Programmierer frei, eine iterative oder eine rekursive Implementation zu wählen. Dabei ist die rekursive Umsetzung meist "eleganter", während die iterative Umsetzung eine bessere Performanz zeigt (insbesondere weil der Stack weniger beansprucht wird und der Overhead für den wiederholten Funktionsaufruf fehlt); siehe auch das Programmierbeispiel unten. Manche Programmiersprachen (insbesondere in der Funktionalen Programmierung) erlauben keine Iteration, so dass immer die rekursive Umsetzung gewählt werden muss. Solche Sprachen setzen häufig zur Optimierung primitive Rekursionen intern als Iterationen um (insbesondere einige Interpreter für Lisp und Scheme tun das).
Es ist zu beachten, dass die rekursive Implementation bei manchen Funktionen (z. B. den Fibonacci-Zahlen) bedingt, dass Teillösungen mehrfach berechnet werden, was eine Verlängerung der Laufzeit bedeutet.
Die Rekursion ist ein wesentlicher Bestandteil einiger Entwurfsstrategien für effiziente Algorithmen, insbesondere der Teile und Herrsche (Divide and Conquer) Strategie. Andere Ansätze (zum Beispiel so genannte Greedy Algorithmen) verlangen ein iteratives vorgehen.
Rekursion und primitiv-rekursive Funktionen spielt eine große Rolle in der theoretischen Informatik, insbesondere in der Komplexitätstheorie und Berechenbarkeitstheorie. Siehe dazu auch Lambda-Kalkül und Ackermann-Funktion. Im Compilerbau ist der rekursive Abstieg (Recursive Descent) eine Technik, bei der eine Sprache rekursiv geparst wird.
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 und iterative Variante, in der Programmiersprache Java.
public class Faculty {
public static void main(String[] args) {
try { System.out.println(args[0]+"! = " + facultyRec(Integer.parseInt(args[0])));}
catch (RuntimeException t) { System.err.println("Ungültiger Parameter !"); }
}
/** Rekursive Methode zur Fakultätsberechnung */
public static long facultyRec(int n) {
if (n==0) {
return 1;
} else {
return n * facultyRec(Math.abs(n) - 1);
}
}
/** Nicht-rekursive (iterative) 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;
}
}
Ein Beispiel für eine primitv rekursive Funktion in Delphi
function Fakultaet(n:integer):integer;
begin
if n <= 1 then result:=1 else
result:= Fakultaet(n-1)*n;
end;
Ein Beispiel für eine indirekte Rekursion in Delphi. Es soll folgende Folge gelöst werden: -1+2-1+2-1+2-...
function TForm1.MinusEins(n:integer):integer;
begin
if n <= 0 then result:=0 else
result:= PlusZwei(n-1)-1;
end;
function TForm1.PlusZwei(n:integer):integer;
begin
if n <= 0 then result:=0 else
result:= MinusEins(n-1)+2;
end;
Ein anderes Beispiel
Ein anderes, recht schön anzusehendes Beispiel ist der rekursive pythagoräische Baum.
Der rekursive Algorithmus sieht hier wie folgt aus:
- Errichte über zwei gegebenen Punkten ein Quadrat
- Auf der Oberseite zeichne ein Dreieck mit definierten Winkeln bzw. Höhe
- Rufe diese Funktion für die beiden Schenkel dieses Dreieckes auf
Dies wird dann bis zu einer vorgegebenen Rekursions-Tiefe wiederholt. Bei der einfachen Rekursion entsteht ein Dreieck mit je einem Quadrat über den drei Seiten. Davon kommt auch der Name „pythagoräische-Baum“.
Nach mehreren Rekursions-Schritten ähnelt das Gebilde dann immer mehr einen Baum.