Eine Methode ruft sich selbst auf
Eine Dosenpyramide hat unten \(n\) Dosen, darüber \(n-1\), ganz oben eine. Wie viele Dosen sind es? Nimm die unterste Reihe weg — übrig bleibt eine kleinere Pyramide derselben Art.
- Rekursion:eine Methode löst ein Problem, indem sie sich selbst für ein kleineres Problem derselben Art aufruft.
- Abbruchbedingung:der einfachste Fall wird ohne Selbstaufruf beantwortet (Rekursionsanfang): eine Pyramide mit 0 Reihen hat 0 Dosen.
- Rekursionsschritt:Selbstaufruf mit verkleinertem Parameter, dessen Ergebnis weiterverarbeitet wird: \(n\) Dosen plus die Pyramide mit \(n-1\) Reihen.
- Rekursive Definition:Fallunterscheidung wie in der Mathematik:
static int dosen(int n) {
if (n == 0) { // Abbruchbedingung
return 0;
}
return n + dosen(n - 1); // Rekursionsschritt
}
Der Selbstaufruf steht in Zeile 5. Aufruf dosen(4) liefert 10.
Der Aufruf mit \(n = 4\) ist nicht der einfachste Fall — er wartet auf \(\text{dosen}(3)\).
Derselbe Rekursionsschritt, jetzt mit \(n = 3\).
Nach zwei weiteren Schritten ist der Parameter bei 0 angekommen.
\(\text{dosen}(0)\) liefert 0 ohne weiteren Aufruf — ab hier werden die wartenden Additionen ausgeführt.
Fünf Aufrufe, der letzte davon ohne Selbstaufruf.
Rekursion: Eine Methode löst ein Problem, indem sie sich selbst für ein kleineres Problem derselben Art aufruft.
Abbruchbedingung: Der einfachste Fall wird ohne Selbstaufruf beantwortet (Rekursionsanfang).
Rekursionsschritt: Selbstaufruf mit verkleinertem Parameter, dessen Ergebnis weiterverarbeitet wird.
Rekursive Definition: Fallunterscheidung wie in der Mathematik:
\[\text{dosen}(n)=\begin{cases}0 & \text{für } n = 0\\ n + \text{dosen}(n-1) & \text{für } n > 0\end{cases}\]
Wann endet die Rekursion?
- Terminierung:die Rekursion endet, wenn jede Aufrufkette nach endlich vielen Schritten die Abbruchbedingung erreicht.
- Bedingung 1:es gibt eine Abbruchbedingung, die ohne Selbstaufruf zurückgibt.
- Bedingung 2:jeder Selbstaufruf bringt den Parameter näher an die Abbruchbedingung — nicht weiter weg.
- Bedingung 3:die Abbruchbedingung wird nicht übersprungen: Wer in Zweierschritten zählt, trifft von einer ungeraden Zahl aus nie die 0.
- Sonst:jeder offene Aufruf belegt Speicher; Java bricht mit
StackOverflowErrorab.
Sechs kurze rekursive Methoden, je ein Aufruf. Tippe zuerst, was der Aufruf liefert — oder ob er nie endet. Dann startest du mit ▶ die Aufrufkette und vergleichst. Die Tipp-Knöpfe erreichst du auch mit Tab und den Pfeiltasten.
Halte fest: Eine Rekursion endet nur, wenn jeder Selbstaufruf der Abbruchbedingung sicher näher kommt. Fehlt sie, läuft der Parameter in die falsche Richtung oder springt er über sie hinweg, folgt ein StackOverflowError.
Rekursive Methode: Abbruchbedingung (Rückgabe ohne Selbstaufruf) plus Rekursionsschritt (Selbstaufruf mit kleinerem Problem).
Terminierung: Jede Aufrufkette erreicht nach endlich vielen Schritten die Abbruchbedingung: Es gibt eine Abbruchbedingung, jeder Selbstaufruf kommt ihr näher, und sie wird nicht übersprungen.
Sonst: Jeder offene Aufruf belegt Speicher, Java bricht mit StackOverflowError ab.
Allgemeine Hinweise
Abbruch vor dem Selbstaufruf
Die Abbruchbedingung muss geprüft werden, bevor sich die Methode selbst aufruft. Steht der Selbstaufruf davor, kommt die Prüfung nie an die Reihe.
Dem Teilergebnis vertrauen
Beim Lesen und Entwerfen nicht jeden Aufruf im Kopf verfolgen: Nimm an, dosen(n - 1) liefert schon das Richtige, und frage nur, was der aktuelle Aufruf noch hinzufügt.
Unzulässige Eingaben
dosen(-1) endet nie, denn −1, −2, … trifft die 0 nicht. Entweder die Voraussetzung \(n \ge 0\) festhalten oder die Abbruchbedingung als n <= 0 schreiben.