Mittel

Rekursion

Funktion ruft sich selbst auf – Basisfall, Rekursionsfall, Vor- und Nachteile.

Warum Priorität „Mittel"? Gelegentlich Teil der Prüfung (40–59%). Verstehen, aber nicht überinvestieren.

Lernziele

Basisfall und Rekursionsschritt identifizieren
Eine rekursive Methode tracen
Laufzeit und Speicherverhalten iterativ vs. rekursiv einschätzen

Prinzip

Eine Funktion löst ein Problem, indem sie sich selbst mit einem kleineren Problem aufruft. Jeder Aufruf belegt einen eigenen Stackframe. Ohne Basisfall wächst der Stack unbegrenzt → StackOverflowError.

Basisfall: Abbruchbedingung, liefert ohne weiteren Aufruf ein Ergebnis.
Rekursionsschritt: löst das Problem durch einen kleineren Teilaufruf.
Endrekursion (tail call): letzter Ausdruck ist der Selbstaufruf – theoretisch optimierbar (Java tut es nicht).

Beispiele

pseudocodeFakultät

FUNKTION fak(n) → INT
    WENN n <= 1 DANN GIB 1 zurück     // Basisfall
    GIB n * fak(n - 1) zurück          // Rekursionsschritt
ENDE FUNKTION

// Trace fak(3) = 3 * fak(2) = 3 * 2 * fak(1) = 3 * 2 * 1 = 6

pseudocodeFibonacci (naiv, O(2^n))

FUNKTION fib(n) → INT
    WENN n < 2 DANN GIB n zurück
    GIB fib(n - 1) + fib(n - 2) zurück
ENDE FUNKTION

Iterativ vs. rekursiv

Rekursiv: eleganter Code für rekursive Strukturen (Bäume, Dateisysteme).
Iterativ: weniger Speicher, meist schneller.
Endrekursive Algorithmen lassen sich immer iterativ umschreiben.

Übungen

SchreibtischtestWelche Ausgabe erzeugt fak(4)?

FUNKTION fak(n)
    WENN n <= 1 DANN GIB 1 zurück
    GIB n * fak(n - 1) zurück
ENDE FUNKTION

GIB fak(4) aus

Deine erwartete Ausgabe

💡 4 * 3 * 2 * 1 = ?

Eine AntwortWas passiert ohne Basisfall?

Eine AntwortLaufzeit des naiven fib(n)?

Zum Weiterlernen

▶

YouTube

Rekursion in JavaScript – Fakultät und Fibonacci schrittweise erklärt

Klassische Rekursions-Beispiele Schritt für Schritt.

▶

YouTube

C Programmieren – Rekursion, Fibonacci-Folge

Alternative Sprache, gut für den Quervergleich.

Externe Inhalte – AP2 Lernhub ist nicht für die Verfügbarkeit oder Korrektheit der verlinkten Seiten verantwortlich.