Das Prinzip Rekursion

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.

• 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 StackOverflowError ab.

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.