Rekursion in Java

Problem

Wie viele Anordnungen gibt es?

Im Regal stehen 5 Bücher. Auf wie viele Arten kannst du sie anordnen? Für den ersten Platz gibt es 5 Möglichkeiten, für den zweiten 4, dann 3, 2 und 1: 5 · 4 · 3 · 2 · 1 = 120. Das ist die Fakultät, geschrieben 5!.

Mit einer Schleife kannst du das schon:

static int factorialLoop(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

System.out.println(factorialLoop(5));

Sieh es auch so: 5! = 5 · 4!. Und 4! = 4 · 3!. Die Aufgabe wird über dieselbe Aufgabe, nur kleiner gelöst. Kann die Methode genau das sagen?

Die Idee

Eine Methode, die sich selbst aufruft

Sie kann. Eine Methode, die sich selbst aufruft, nennt man rekursiv, und das Vorgehen Rekursion.

static int factorial(int n) {
    if (n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

System.out.println(factorial(5));

Zwei Dinge sorgen dafür, dass es funktioniert:

Ein Basisfall. Ein Fall, der direkt gelöst wird, ohne neuen Aufruf. Hier: 1! = 1.
Eine kleinere Aufgabe. Jeder Aufruf ruft sich selbst mit einer Zahl auf, die näher am Basisfall liegt: n - 1.

Sieh es dir an

Der Stapel der Aufrufe

static int factorial(int n) {
    if (n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

System.out.println(factorial(3));  // 6

Schritt für Schritt, in Worten

main ruft factorial(3) auf.
Neuer Speicher für factorial mit n = 3.
3 ist nicht 1, also ruft die Methode factorial(2) auf und wartet auf die Antwort.
Dasselbe noch einmal: factorial(2) ruft factorial(1) auf. Jeder Aufruf hat sein eigenes n.
n ist 1: Das ist der Basisfall. Er gibt 1 zurück, ohne sich noch einmal aufzurufen.
Die Antwort geht nach unten zurück: 2 * 1 = 2.
Und noch einmal: 3 * 2 = 6.
factorial(3) gibt 6 zurück, und main gibt es aus.

Jeder Aufruf bekommt seinen eigenen Speicher mit seinem eigenen n. Sie stapeln sich übereinander und warten. Diesen Stapel nennt man Aufrufstapel (call stack). Wenn der Basisfall 1 zurückgibt, gehen die Antworten eine nach der anderen nach unten zurück, und der Stapel löst sich auf.

Probier es aus

Runter und wieder rauf

Was gibt das Programm aus?

static void steps(int n) {
    if (n == 0) {
        return;
    }
    System.out.println("runter " + n);
    steps(n - 1);
    System.out.println("rauf " + n);
}

steps(2);

Antwort

runter 2
runter 1
rauf 1
rauf 2

runter 2
runter 1
rauf 2
rauf 1

runter 2
rauf 2
runter 1
rauf 1

Probier es aus

Finde den Fehler

sumTo(4) soll 1 + 2 + 3 + 4 = 10 zurückgeben. Stattdessen bricht das Programm mit StackOverflowError ab. In welcher Zeile ist der Fehler?

Wähle die Zeile mit dem Fehler.

Die Idee

Rekursion oder Schleife?

Die Fakultät lässt sich mit einer Schleife oder mit Rekursion schreiben. Hier ist die Schleife die bessere Wahl: Sie häuft nicht für jeden Aufruf Speicher an, und für 100 000 Aufrufe reicht der Stapel nicht.

Rekursion ist dort natürlich, wo eine Sache kleinere Sachen derselben Art enthält: ein Ordner mit Ordnern darin, eine Kategorie mit Unterkategorien, ein Ast mit Ästen. Solchen Aufgaben begegnest du später im Kurs. Dort wird eine Schleife umständlich, während die rekursive Methode kurz bleibt.

Genauer, für Neugierige

Die Fakultät schreibt man oft mit dem Basisfall 0! = 1 (if (n == 0)). Dann funktioniert sie auch für 0.

Ein int reicht bis 12!. Für 13! passt das Ergebnis nicht mehr hinein, und die Zahl kommt falsch heraus. Für größere Werte nimm long.

Probier es aus

Bring die Zeilen in die richtige Reihenfolge

Die Methode soll eine Potenz berechnen: power(2, 10) ist 1024. Bring ihre Zeilen in die richtige Reihenfolge.

return 1;
}
return base * power(base, exp - 1);
if (exp == 0) {
static int power(int base, int exp) {
}

Übung

Rekursive Aufgaben

1. Fakultät auf zwei Arten. Schreib factorialLoop(int n) mit einer for-Schleife und factorial(int n) mit Rekursion. Lies eine Zahl ein und gib das Ergebnis beider Methoden aus.

Die Fakultät von 5 ist 120
Die Fakultät von 5 ist 120

2. Quersumme. sumDigits(int n): die letzte Ziffer (n % 10) plus die Quersumme des Rests (n / 10). Der Basisfall ist eine einstellige Zahl.

3. Fibonacci. Jede Zahl ist die Summe der zwei davor: 0, 1, 1, 2, 3, 5, 8… fib(int n) gibt die n-te Zahl zurück. Probier es mit 10 und dann mit 45. Warum ist es so langsam? Hinweis: Wie oft wird jede Zahl ausgerechnet?

4. Palindrom. isPalindrome(String s): Der erste und der letzte Buchstabe sind gleich, und die Mitte ist ein Palindrom. Der Basisfall ist ein Wort mit 0 oder 1 Buchstaben.

sumDigits(2024)
fib(10)
isPalindrome("neben")
isPalindrome("ABCDE")

8
55
true
false

Test

Teste dich

1. Was ist Rekursion?Eine Methode, die sich selbst aufruftEine Schleife in einer MethodeZwei Methoden mit demselben Namen

2. Warum braucht eine rekursive Methode einen Basisfall?Damit sie aufhört, sich selbst aufzurufenDamit sie schneller läuftDamit sie ein Ergebnis zurückgeben kann

3. factorial(3) ruft factorial(2) auf, und das ruft factorial(1) auf. Wie viele Variablen n sind im Speicher, kurz bevor factorial(1) zurückkehrt?KeineDreiEine

4. Was passiert, wenn der Basisfall nie erreicht wird?Der Stapel läuft über, und das Programm bricht mit einem Fehler abDie Methode gibt 0 zurückDas Programm läuft ewig, ohne Fehler

Rekursion

Cookies