Funktionen, die sich selbst aufrufen. Mit Call-Stack-Visualisierung am Beispiel Fakultät.
Rekursion ist wenn eine Funktion sich selbst aufruft, mit einem kleineren Teilproblem als Eingabe, bis ein Basisfall erreicht ist. Für viele Probleme (Fakultät, Fibonacci, Baum-Traversierung, Divide-and-Conquer) ist Rekursion die natürlichste Lösung.
Die zwei Pflicht-Bestandteile jeder rekursiven Funktion:
In Klausuren wirst du oft gefragt: schreibe eine rekursive Funktion für Fakultät / Fibonacci oder trace die Aufrufe für factorial(4) Schritt für Schritt. Pro Aufruf eine Zeile aufschreiben mit aktuellem Argument und Rückgabewert.
Die Fakultät einer Zahl n ist n × (n-1) × (n-2) × ... × 1. Mathematisch:
n! = n × (n-1)!
Genau das schreiben wir auch im Code:
public static int fakultaet(int n) {
if (n <= 1) {
return 1; // Basisfall
}
return n * fakultaet(n - 1); // Rekursiver Aufruf
}fakultaet(4) führt zu vier verschachtelten Aufrufen, die nacheinander zurückgeben:
fakultaet(4)
= 4 * fakultaet(3)
= 4 * 3 * fakultaet(2)
= 4 * 3 * 2 * fakultaet(1)
= 4 * 3 * 2 * 1
= 24Jeder Aufruf landet auf dem Call Stack und wartet, bis die tieferen Aufrufe fertig sind. Erst dann wird zurückgerechnet. Im interaktiven Abschnitt kannst du das Schritt für Schritt selbst sehen.
Alle Tabs der Lerneinheit (Erklärung · Interaktiv · Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur — und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Rekursion ist wenn eine Funktion sich selbst aufruft, mit einem kleineren Teilproblem als Eingabe, bis ein Basisfall erreicht ist. Für viele Probleme (Fakultät, Fibonacci, Baum-Traversierung, Divide-and-Conquer) ist Rekursion die natürlichste Lösung.
Wie speichert ein Programm Werte? Wie unterscheiden sich int, double, String und boolean?
if, else, else if. Wie trifft ein Programm Entscheidungen, und welche Vergleichsoperatoren brauchst du?
for, while, Iteration. Wie wiederhole ich Code, ohne mich zu verzetteln?
Die zwei Pflicht-Bestandteile jeder rekursiven Funktion:
In Klausuren wirst du oft gefragt: schreibe eine rekursive Funktion für Fakultät / Fibonacci oder trace die Aufrufe für factorial(4) Schritt für Schritt. Pro Aufruf eine Zeile aufschreiben mit aktuellem Argument und Rückgabewert.
Die Fakultät einer Zahl n ist n × (n-1) × (n-2) × ... × 1. Mathematisch:
n! = n × (n-1)!
Genau das schreiben wir auch im Code:
public static int fakultaet(int n) {
if (n <= 1) {
return 1; // Basisfall
}
return n * fakultaet(n - 1); // Rekursiver Aufruf
}def fakultaet(n):
if n <= 1:
return 1 # Basisfall
return n * fakultaet(n - 1) # Rekursiver AufrufJede rekursive Funktion braucht:
n <= 1 gibt 1 zurück.Wenn der Basisfall fehlt, ruft die Funktion sich endlos selbst auf. Stack overflow.
fakultaet(4) führt zu vier verschachtelten Aufrufen, die nacheinander zurückgeben:
fakultaet(4)
= 4 * fakultaet(3)
= 4 * 3 * fakultaet(2)
= 4 * 3 * 2 * fakultaet(1)
= 4 * 3 * 2 * 1
= 24fakultaet(4)
= 4 * fakultaet(3)
= 4 * 3 * fakultaet(2)
= 4 * 3 * 2 * fakultaet(1)
= 4 * 3 * 2 * 1
= 24Jeder Aufruf landet auf dem Call Stack und wartet, bis die tieferen Aufrufe fertig sind. Erst dann wird zurückgerechnet. Im interaktiven Abschnitt kannst du das Schritt für Schritt selbst sehen.
Wann nicht: einfache Schleifen sind oft schneller und klarer.
Wähle einen Wert für n und folge dem Stack. Du siehst zuerst, wie sich Aufrufe stapeln (jeder wartet auf den nächsten), dann wird der Basisfall erreicht und die Rückgabe rollt zurück.
Interaktive Visualisierung
Visualisiert den Call-Stack während rekursiver Aufrufe inkl. Stack-Frames.
Wichtig: der Stack ist begrenzt. Bei n = 100000 würde Java einen StackOverflowError werfen. Genau deshalb gibt es Tail-Rekursion und iterative Versionen als Alternative für tiefe Rekursion.
Sechs Fragen zu Base Case, Stack-Overflow und Klausur-Klassikern wie Fakultät / Fibonacci.
Klausurfragen mit Lösungen (6)
Antwort: Eine Funktion, die sich selbst aufruft
Erklärung: Rekursion = eine Funktion ruft sich selbst auf. Beispiel: `fakultaet(n) { return n * fakultaet(n-1); }`. Wichtig: jede rekursive Funktion braucht einen Base Case der ohne weiteren Selbstaufruf zurückkehrt — sonst Endlosschleife.
Antwort: Sie verursacht einen Stack Overflow
Erklärung: Ohne Base Case ruft sich die Funktion endlos selbst auf. Jeder Aufruf legt einen neuen Stack-Frame an, bis der Stack voll ist → StackOverflowError (Java) bzw. RecursionError (Python). Klausur-Klassiker.
Antwort: Wahr
Erklärung: Stimmt. Der Base Case ist die Abbruch-Bedingung — der Wert für den die Funktion ohne weiteren Selbstaufruf zurückkehrt. Z.B. `if (n <= 1) return 1;` für Fakultät. Ohne Base Case = Endlosschleife = Stack Overflow.
Typ: Wahr/Falsch
public static int fakultaet(int n) {
if (n <= 1) return 1;
return n * fakultaet(n - 1);
}
fakultaet(4); // ?Antwort: 24
Erklärung: fakultaet(4) = 4 * fakultaet(3) = 4 * 3 * fakultaet(2) = 4 * 3 * 2 * fakultaet(1) = 4 * 3 * 2 * 1 = 24. Der Base Case `n <= 1` returnt 1. Klassische Klausur-Aufgabe: Rekursion Schritt für Schritt durchspielen.
Antwort: 5 Aufrufe
Erklärung: fakultaet(5) → fakultaet(4) → fakultaet(3) → fakultaet(2) → fakultaet(1). Total: 5 Aufrufe. Der Base Case bei n=1 returnt direkt ohne weiteren Selbstaufruf.
Typ: Zahlen-Eingabe
Richtige Antworten: Iteration nutzt Schleifen, Rekursion nutzt Selbstaufrufe; Jede rekursive Funktion lässt sich auch iterativ schreiben; Rekursion ist oft eleganter bei Baum-/Listen-Strukturen
Erklärung: Wahr: (1) Iteration = Schleifen, Rekursion = Selbstaufrufe. (3) Jede rekursive Funktion ist iterativ umschreibbar (Stack-Simulation). (5) Bei Bäumen/Listen ist Rekursion oft natürlicher. Falsch: Rekursion ist NICHT immer langsamer (oft gleich, manchmal sogar schneller mit Tail-Call-Optimierung). Plus: Rekursion VERBRAUCHT Stack-Speicher (jeder Aufruf = neuer Frame).
Typ: Multi-Select
Geordnete Sammlungen mit Index-Zugriff. Statisches Array (fixe Größe) vs dynamische Liste (ArrayList, list). Welche Operationen sind O(1), welche O(n)? Klausurwichtige Datenstruktur Nummer 1.