Rekursion
Als rekursiv wird ein Programm oder Algorithmus bezeichnet, das/der sich selbst direkt oder indirekt aufruft.
Rekursionen und Schleifen sind semantisch äquivalent und können daher durch durch das jeweils andere ersetzt werden. Dies ist jedoch nicht immer sinnvoll.
Rekursion kommt vom lateinischen Wort recurrere, was zurücklaufen bedeutet.
Inhaltsverzeichnis
Erstes Beispiel für eine Rekursion[1]
Fakultät[2]von n
Eingabe: Eine natürliche Zahl n Ausgabe: Die Fakultät von n Vorgehensweise: Wenn n gleich 0, dann gib 1 zurück, ansonsten gib das Produkt von n und dem Algorithmus mit der Eingabe n-1 zurück.
Ausführung mit n = 3
Aufbau der Rekursion ("Hinweg")
Ebene: n = 3
Ausführung: n ist ungleich 0, berechne daher das Produkt von 3 und (3-1)!
Aufruf: Fakultät(2)
Ebene: n = 2
Ausführung: n ist ungleich 0, berechne daher das Produkt von 2 und (2-1)!
Aufruf: Fakultät(1)
Ebene: n = 1
Ausführung: n ist ungleich 0, berechne daher das Produkt von 1 und (1-1)!
Aufruf: Fakultät(0)
Ebene: n = 0
Ausführung: n ist nun gleich 0, gib also 1 zurück
Abbau der Rekursion ("Rückweg")
Rückgabe: Fakultät(0) = 1
Ebene: n = 1
Rückgabe: 1 * 1 = 1
Ebene: n = 2
Rückgabe: 2 * 1 = 2
Ebene: n = 3
Rückgabe: 3 * 2 = 6
Mathematisch notiert sieht das ganze folgendermaßen aus:
3! = 3 * 2! = 3 * 2 * 1! = 3 * 2 * 1 * 0! = 3 * 2 * 1 * 1 = 3 * 2 * 1 = 3 * 2 = 6
Aufbau einer Rekursion
Jede Rekursion besteht aus einer Abbruch-/Terminierungsbedingung und einem Rekursionsrumpf.
Der Rekursionsabbruch erfolgt, wenn die Terminierungsbedingung erfüllt ist. Diese Bedingung überprüft, ob die unterste Ebene des Rekursionsbaums erreicht wurde. Im obigen Beispiel ist dies die Überprüfung, ob n gleich 0 ist, da 0! gleich 1 ist. Sollte diese Bedingung nicht erfüllt werden, wird der Rekursionsrumpf ausgeführt. Wichtig für eine funktionierende Rekursion ist, dass die Bedingung irgendwann erreicht wird, da ansonsten die Rekursion nicht terminiert (Endlosrekursion).
Im Rekursionsrumpf geschieht der Aufruf der Funktion für eine niedrigere Ebene und die Berechnung des Ergebnisses der aktuellen Ebene mit diesem. In dem Beispiel ist dies der Ansonsten-Pfad.
Zweites Beispiel
Ist die Zahl n grade?
1. Funktion
Eingabe: Eine natürliche Zahl n
Ausgabe: Ja, wenn n gerade ist, Nein, wenn n ungerade ist.
Vorgehensweise:
Wenn n gleich 0 ist, dann gebe Ja zurück,
ansonsten gebe das Ergebnis der 2. Funktion für n-1 zurück.
2. Funktion
Eingabe: Eine natürliche Zahl n
Ausgabe: Ja, wenn n ungerade ist, Nein, wenn n gerade ist.
Vorgehensweise:
Wenn n gleich 0 ist, dann gebe Nein zurück,
ansonsten gebe das Ergebnis der 1. Funktion mit n-1 zurück.
Ausführung mit n = 5
Aufbau der Rekursion ("Hinweg")
1. Funktion wird mit n = 5 aufgerufen
n ist ungleich 0, daher führe 2. Funktion mit n = 5-1 = 4 aus
2. Funktion mit n = 4
n ist ungleich 0, daher führe 1. Funktion mit n = 4-1 = 3 aus
1. Funktion mit n = 3
n ist ungleich 0, daher führe 2. Funktion mit n = 3-1 = 2 aus
2. Funktion mit n = 2
n ist ungleich 0, daher führe 1. Funktion mit n = 2-1 = 1 aus
1. Funktion mit n = 1
n ist ungleich 0, daher führe 2. Funktion mit n = 1-1 = 0 aus
2. Funktion mit n = 0
n ist gleich 0, daher
Rückgabe: Nein
Abbau der Rekursion ("Rückweg")
1. Funktion mit n = 1
Rückgabe: Nein
2. Funktion mit n = 2
Rückgabe: Nein
1. Funktion mit n = 3
Rückgabe: Nein
2. Funktion mit n = 4
Rückgabe: Nein
1. Funktion mit n = 5
Rückgabe: Nein
=> 5 ist ungerade
Direkte und indirekte Rekursion
Bei der direkten Rekursion ruft sich die Funktion bei der Rückgabe selbst wieder auf. Dies trifft auf das erste Beispiel zu.
Bei der indirekten Rekursion ruft Funktion f eine andere Funktion g auf, die wiederum f aufruft. Dies geschieht im zweiten Beispiel.
Verwendung von Rekursion
Fußnoten
- ↑ Alle Rekursionsbeispiele werden hier zum besseren Verständnis im sogenannten Pseudocode notiert.
- ↑ Die Fakultät einer Zahl ist das Produkt aller natürlichen Zahlen (außer 0), die kleiner oder gleich dieser Zahl sind. Fakultät wird mit einem Ausrufezeichen hinter der Zahl notiert. Die Fakultät von 0 ist 1 (0! = 1).
