Thema in Kurzform
Unter rekursiver Programmiererung versteht man eine Methode, die sich selbst aufruft.
Wichtiger Bestandteil der Rekursion ist die Abruchbedingung innerhalb der Methode, da sonst das Programm in der Rekursion gefangen bleibt.
Unterschied iterativ und rekursiv
Wenn wir ein bestimmtes Problem durch einen Algorithmus lösen wollen, stehen uns zwei Vorgehensweisen zur Wiederholung zur Verfügung:
- iterativ: Wir führen eine Aktion mithilfe von Schleifen wiederholt durch.
- rekursiv: Die Wiederholung der Aktion erfolgt dadurch, dass sich eine Methode selbst (mehrmals) aufruft.
Sehen wir uns kurz noch ein Beispiel für den bekannten iterativen Ansatz mit einer while-Schleife an:
int i = 0;
while(i < 10){
System.out.print(++i + " ");
} Output: 1 2 3 4 5 6 7 8 9 10
Und jetzt rekursiv!
Um diese Lösung rekursiv umzusetzen, brauchen wir eine Methode, die sich selbst aufruft. Wir nennen eine solche Methode dann rekursive Methode.
Eine rekursive Methode mit passender Klasse sieht dann so aus:
public class Rekursiv {
public static int i = 0;
public static void rekursiveMethode() {
i++;
System.out.print(i + " ");
if (i < 10) {
rekursiveMethode(); // Rekursion!
}
}
public static void main(String[] args) {
rekursiveMethode();
}
} Jeder rekursive Methodenaufruf packt ein neues Element zum Abarbeiten auf den Stack der JVM.
Deshalb ist eine zentrale Bedingung für das ordentliche Funktionieren einer rekursiven Methode das Vorhandensein einer Abbruchbedingung (hier i < 10). Ohne diese "explodiert" der Stack und unser unser Code wird unweigerlich einen java.lang.StackOverflowError erzeugen und krepieren.
Rekursion mit Parameter und Rückgabetyp
Im Beispiel oben, haben wir eine sehr einfache rekursive Methode programmiert. Oftmals ist es aber nicht ganz so simpel und wir brauchen "vollwertige" Methoden mit Parametern und Rückgabetyp.
Das nächste Beispiel zeigt eine solche Methode. Wir nennen sie sum() und verwenden sie, um alle Zahlen zwischen 1 und 6 zu summieren:
public class Rekursiv {
public static void main(String[] args) {
int result = sum(6);
System.out.println(result);
}
public static int sum(int n) {
if (n > 0) {
return n + sum(n - 1); // Rekursion
} else {
return 0;
}
}
}Das Ergebnis der Rekursion lautet 21.
Doch wie kommt es dazu? Schauen wir uns Schritt für Schritt an, was die Methode macht:
Die Methode sum() hat einen Parameter n für eine Ganzzahl. Beim ersten Initial-Aufruf in der Main-Methode ist das konkret der Wert 6. Bei den folgenden rekursiven Aufrufen wird n - 1 als Argument übergeben und zwar solange, wie ngrößer ist als 0 (= Abbruchbedingung). Der letzte rekursive Aufruf lautet damit sum(0).
Jeder Methodenaufruf liefert auch einen entsprechenden Wert zurück, der auf nsummiert wird.
Die Rekursion stoppt, wenn n den Wert 0 hat. Dann wird 0 zurückgeliefert und es folgt kein weiterer Aufruf. Die Rekursion ist beendet und die Summe von 21 ist gebildet.
In der Gesamtheit absolviert die Rekursion folgende Einzelschritte:
6 + sum(5)
6 + ( 5 + sum(4) )
6 + ( 5 + ( 4 + sum(3) ) )
6 + ( 5 + ( 4 + ( 3 + sum(2) ) ) )
6 + ( 5 + ( 4 + ( 3 + ( 2 + sum(1) ) ) ) )Genauer betrachtet: der Stack
Bei der Rekursionsfolge werden die einzelnen Methodenaufrufe im Stack (= "Stapelspeicher") aufgetürmt. Die Abarbeitung des Stacks erfolgt dabei nach dem "Last-In-First-Out"-Prinzip. Das bedeutet, dass die Methoden umgekehrt ihrer Aufruf-Reihenfolge abgearbeitet werden: Die erste aufgerufene Methode wird als letztes ausgeführt und die letzte wird als erstes aufgerufen.
Hier eine Infografik, die dir das Prinzip für das Beispiel der rekursiven Funktion sum() zeigt:
Lineare vs. verzweigte Rekursion
Es gibt schließlich noch einen Unterschied zwischen der linearen und der verzweigten Rekursion:
- Lineare Rekursion: Bei der linearen Rekursion löst ein rekursiver Aufruf höchstens einen einzigen weiteren Aufruf aus.
- Verzweigte Rekursion: Die verzweigte Rekursion führt zu zwei oder mehrweiteren Aufrufen. Das hat zur Folge, dass die Anzahl der rekursiven Aufrufe exponentiell ansteigt.
Die lineare Rekursion haben wir mit den beiden rekursiven Methoden von oben ja bereits kennengelernt. Sehen wir uns jetzt ein Beispiel für die verzweigte Rekursion an.
Dazu wollen wir ein kleines Programm schreiben, dass den Wert einer bestimmten Position innerhalb der Fibonacci-Folge ermittelt.
Die Fibonacci-Folge ist eine Reihe von Zahlen, in der jede Zahl außer der ersten und der zweiten die Summe ihrer beiden Vorgänger ist:
0, 1, 1, 2, 3, 5, 8, 13, ...
Die allgemeine Formel dazu lautet:
fib(n) = fib(n-1) + fib (n-2)
Um die Fibonacci-Zahl an einer bestimmten Position n zu erhalten, bauen wir diese verzweigte rekursive Funktion zusammen:
public class RecursiveFibonacciSequence {
public static void main(String[] args) {
int fibonacciNumber = getFibonacciNumberAt(6);
System.out.println(fibonacciNumber); // 8
}
public static int getFibonacciNumberAt(int n) {
if (n < 2) {
return n;
} else
return getFibonacciNumberAt(n - 1) + getFibonacciNumberAt(n - 2);
}
} Konkret wollen wir hier mit dem Aufruf getFibonacciNumberAt(6) die sechste Fibonacci-Zahl und erhalten korrekt den Wert 8 zurückgeliefert..
