Rekursion: Prinzip und Aufrufe
Eine rekursive Methode löst ein Problem, indem sie sich selbst für ein kleineres Problem derselben Art aufruft — bis ein einfachster Fall ohne Selbstaufruf erreicht ist.
Abbruchbedingung und Rekursionsschritt
Der einfachste Fall wird direkt beantwortet (Rekursionsanfang); sonst ruft sich die Methode mit einem kleineren Parameter auf und verarbeitet dessen Ergebnis.
return n + dosen(n - 1);Terminierung
Es gibt eine Abbruchbedingung, jeder Selbstaufruf kommt ihr näher und überspringt sie nicht. Sonst: StackOverflowError.
f(n - 2) trifft 0 nur bei geradem nAufrufstapel
Jeder offene Aufruf hat einen eigenen Rahmen (Parameter, lokale Variablen, Rücksprungstelle). Abstieg legt Rahmen auf, Aufstieg nimmt sie ab — der zuletzt begonnene Aufruf endet zuerst.
Aufrufbaum
Lineare Rekursion (ein Selbstaufruf) bildet eine Kette, Baumrekursion (zwei oder mehr) einen Baum, der von links in die Tiefe durchlaufen wird.
fib(n - 1) + fib(n - 2)Beispiel fakultaet(4): Abstieg bis fakultaet(1) = 1, Aufstieg 2, 6, 24. Vier Aufrufe, Tiefe 4. Anweisungen nach dem Selbstaufruf laufen in umgekehrter Reihenfolge.
Aufrufe ≠ Tiefe
Der Aufrufbaum von fib(4) hat 9 Knoten, die Tiefe ist aber nur 4. Für den Speicher zählt die Tiefe, für die Rechenzeit die Zahl aller Aufrufe.
Rekursiv entwerfen und einsetzen
Rekursive Lösungen entstehen nach einem festen Rezept. Ob sie sinnvoll sind, entscheidet der Vergleich mit der Schleife.
Entwurfsrezept
Festlegen, was die Methode liefert · Problem durch ein kleineres derselben Art ausdrücken · einfachsten Fall ohne Selbstaufruf lösen · Teilergebnis verwenden · Terminierung prüfen.
n % 10 + quersumme(n / 10)Hilfsparameter
Wird die Reihung nicht kürzer, beschreibt ein zusätzlicher Parameter das Restproblem (Index i oder Grenzen links, rechts). Eine Startmethode versteckt ihn.
maximum(a) → maximum(a, 0)Zeichenketten
Erstes Zeichen abtrennen und mit dem Rest rekursiv weiterarbeiten; Abbruch beim leeren oder einstelligen String.
umkehren(s.substring(1)) + s.charAt(0)Binäre Suche rekursiv
Mitte ansehen, bei Treffer Index zurückgeben, sonst nur in einer Hälfte weitersuchen; leerer Bereich (links > rechts) liefert −1.
binSuche(a, x, mitte + 1, rechts)Beide sind gleich mächtig. Endrekursion (return f(…) als letzte Aktion) lässt sich direkt als Schleife schreiben. Baumrekursion mit überlappenden Teilproblemen wie fib wächst exponentiell: \(A(n) = 2\,\text{fib}(n+1) - 1\) Aufrufe.
Rekursion kostet Speicher
Lineare Rekursion hat Tiefe \(n\) — bei 100 000 Elementen droht ein StackOverflowError. Eine Schleife braucht nur einen Rahmen.
Teile und herrsche: Mergesort und Quicksort
Teilen, Teilprobleme rekursiv lösen, zusammenführen. Der Gewinn entsteht, wenn in Hälften geteilt wird — dann gibt es nur \(\log_2 n\) Ebenen.
Strategie
Teilen in Teilprobleme derselben Art · Herrschen: rekursiv lösen · Zusammenführen der Teillösungen · Basisfall direkt lösen. Grenzen links, rechts statt Kopien.
mitte = (links + rechts) / 2Mergesort
Hälften ohne Vergleich bilden, beide rekursiv sortieren, dann mischen: immer das kleinere Front-Element in die Hilfsreihung, Rest ohne Vergleich. Stabil mit <=.
Quicksort
Am Pivot zerlegen: Werte ≤ Pivot nach links, größere nach rechts, Pivot dazwischen an seinen endgültigen Platz; beide Teile rekursiv. Zusammenführen entfällt.
quicksort(a, links, p - 1)Pivot-Wahl
Letztes Element: bei sortierter Eingabe ungünstigster Fall. Mittleres Element oder Median aus drei halbieren vorsortierte Bereiche; vorher ans Ende tauschen.
\(\log_2 n\) Ebenen mit je höchstens \(n\) Vergleichen. Beispiel \(n = 64\): 384. Das rekursive Maximum mit \(V(n) = 2V\!\left(\frac{n}{2}\right) + 1\) braucht dagegen \(n - 1\) Vergleiche — so viele wie eine Schleife.
Gegenstücke
Mergesort arbeitet beim Zusammenführen und teilt ohne Arbeit; Quicksort arbeitet beim Teilen und muss nichts zusammenführen. Die binäre Suche löst nur eine Hälfte und führt nichts zusammen.
Beurteilen — und die Regeln, an denen die Punkte hängen
Beurteilt wird nach Laufzeit in allen Fällen, Zusatzspeicher, Rekursionstiefe und Stabilität. In Klausuren gehen die meisten Punkte bei Abbruchbedingungen, beim Zählen und bei unbegründeten Urteilen verloren.
| Verfahren | günstig | ungünstig | Zusatzspeicher | Tiefe | stabil? |
|---|---|---|---|---|---|
| Selectionsort | \(\frac{n(n-1)}{2}\) | \(\frac{n(n-1)}{2}\) | keiner | iterativ | nein |
| Insertionsort | \(n-1\) | \(\frac{n(n-1)}{2}\) | keiner | iterativ | ja |
| Mergesort | \(\frac{n}{2}\log_2 n\) | \(\le n\log_2 n\) | Hilfsreihung \(n\) | \(\log_2 n + 1\) | ja |
| Quicksort | \(\approx n\log_2 n\) | \(\frac{n(n-1)}{2}\) | keiner (Stapel) | \(\log_2 n\) bis \(n\) | nein |
Regel 1 — Abbruch zuerst prüfen
Jede rekursive Methode mit dem kleinsten Fall testen: Wird die Abbruchbedingung erreicht, und liefert sie das Richtige? Bei Bereichen links … rechts auch zwei Elemente testen.
Regel 2 — Aufrufe sauber mitschreiben
Aufrufbaum oder eingerückte Aufrufkette mit Parametern und Rückgabewerten; beim Aufstieg die Rückgabewerte in umgekehrter Reihenfolge eintragen.
Regel 3 — Vereinbart zählen
Vorher festlegen, was gezählt wird: Aufrufe, Vergleiche, Tiefe. Formeln an einem kleinen Beispiel prüfen, etwa \(n = 8\): Mergesort höchstens 17 Vergleiche, \(n\log_2 n = 24\).
Regel 4 — Urteile mit allen Fällen begründen
Nicht „Quicksort ist schnell“, sondern: im Mittel \(\approx n\log_2 n\), bei sortierter Eingabe mit letztem Pivot \(\frac{n(n-1)}{2}\) und Tiefe \(n\); Mergesort garantiert \(n\log_2 n\), braucht aber \(n\) Zusatzspeicher.