1. Einleitung
Rekursion klingt wie ein Akt programmatischer Narzissmus: eine Funktion schaut in den Spiegel und ruft sich noch einmal. In Wirklichkeit ist es aber eine sehr disziplinierte Technik. Eine rekursive Funktion muss einem Vertrag folgen: sie hat einen Moment, in dem sie aufhört, sich selbst aufzurufen, und es gibt eine Regel, wie sie diesem Moment näherkommt. Diese zwei Elemente sind „Basis“ und „Schritt“.
Praktisch gesprochen besteht Rekursion aus zwei Teilen.
Der erste Teil — der Basisfall (base case): die Situation, in der die Aufgabe so klein ist, dass die Antwort offensichtlich ist und kein weiterer Selbstaufruf nötig ist.
Der zweite Teil — der rekursive Schritt (recursive step): die Regel, wie man aus der aktuellen Aufgabe eine ähnliche, aber kleinere macht, und die Funktion erneut aufruft.
Schemahaft lässt sich das so darstellen:
flowchart TD
A["Aufgabe"] --> B{"Ist die Aufgabe schon einfach?"}
B -->|ja| C["Antwort sofort (Basis)"]
B -->|nein| D["Löse eine \"etwas kleinere\" Aufgabe per Rekursion (Schritt)"]
D --> E["Baue die Antwort für die aktuelle Aufgabe zusammen"]
2. Basisfall: der Punkt, an dem wir aufhören, tiefer zu gehen
Der Basisfall ist kein Schmuckstück und nicht bloß ein „na gut, fügen wir ein if ein, damit der Compiler nicht meckert“. Er ist der zentrale Teil einer rekursiven Funktion. Er beantwortet die Frage: wann hören wir auf, Selbstaufrufe zu erzeugen und beginnen, die Aufrufe wieder zurückzugeben. In der vorherigen Vorlesung habt ihr gesehen, dass jeder Aufruf einen Stack-Frame erzeugt; der Basisfall ist der Punkt, an dem keine neuen Frames mehr erstellt werden.
Das einfachste Beispiel ist die Summe der Zahlen von 1 bis n.
Beispiel: Summe von 1 bis n — Basisfall
Beginnen wir mit der Definition: sum_to(n) gibt 1 + 2 + ... + n zurück. Dann ist es logisch zu sagen:
- wenn n == 0, ist die Summe 0 (das ist die Basis),
- ansonsten gilt sum_to(n) = n + sum_to(n - 1) (das ist der Schritt, dazu gleich mehr).
Der Code für den Basisfall sieht so aus:
int sum_to(int n) {
if (n == 0) return 0; // Basis: Summe bis 0 ist 0
return n + sum_to(n - 1);
}
Beachte: die Basisantwort 0 ist hier nicht zufällig. Sie ist das sogenannte „neutrale Element“ zur Addition: wenn man etwas addiert, ist es praktisch, mit Null zu beginnen.
Beispiel: Fakultät — Basisfall
Die Fakultät n! ist 1 * 2 * 3 * ... * n. Logisch ist:
- 0! = 1 — das ist die Basis,
- n! = n * (n - 1)! — das ist der Schritt.
long long factorial(int n) {
if (n == 0) return 1; // Basis: 0! = 1
return n * factorial(n - 1);
}
Auch hier ist 1 nicht „weil's im Lehrbuch so steht“. Es ist das neutrale Element der Multiplikation. Bei einem Produkt ist es praktisch, das leere Produkt als 1 zu betrachten.
Die Basis als „kleinster Baustein“ der Aufgabe
Eine passende Analogie (ja, etwas alltäglich, aber nützlich): stell dir vor, du baust Möbel nach Anleitung. Der rekursive Schritt ist „baue ein kleineres Modul und schraube es dann hier fest“. Der Basisfall ist „nimm ein einzelnes Brett“. Wenn die Anleitung niemals sagt „das ist das kleinste Teil, teil es nicht weiter“, wirst du den Schrank endlos halbieren und niemals eine Schraube eindrehen.
Tabelle: wie man schnell den Basisfall findet
| Aufgabe | Was wird verkleinert? | Basisfall | Basisantwort |
|---|---|---|---|
| Summe 1..n | |
|
|
| Fakultät n! | |
|
|
| GGT (gcd) | |
|
|
| Durchlauf eines Strings per Index | |
|
„nichts tun“ |
Die letzte Zeile ist wichtig: die Antwort ist nicht immer eine Zahl. Manchmal ist die Basis einfach der Punkt, an dem die Funktion aufhört (zum Beispiel beim Ausgeben von Zeichen).
3. Rekursiver Schritt: mache die Aufgabe kleiner und rufe dich erneut auf
Der rekursive Schritt ist der Teil, der Rekursion überhaupt erst zur Rekursion macht: wir nehmen die Ausgangsaufgabe und reduzieren sie auf dieselbe, aber kleinere Aufgabe. Wichtig ist hier nicht nur „sich selbst aufzurufen“, sondern die Parameter so zu verändern, dass wir zur Basis hinbewegen. Wenn die Parameter sich nicht ändern (oder sich in die falsche Richtung ändern), wird die Funktion sich unendlich oft aufrufen.
Der rekursive Schritt hat typischerweise zwei Komponenten.
Die erste Komponente — das Ergebnis der kleineren Aufgabe per Selbstaufruf erhalten.
Die zweite Komponente — das Ergebnis für die aktuelle Ebene „weitermontieren“ (z. B. n addieren, mit n multiplizieren, ein Zeichen ausgeben).
Vorlage einer rekursiven Funktion
Nachfolgend ein nützliches „Skelett“ (keine Magie, nur eine übliche Denkordnung):
ReturnType f(Args...) {
if (base_condition) {
return base_value; // Basis
}
// Aufgabe verkleinern
auto smaller = f(modified_args); // Schritt: Selbstaufruf
// Antwort zusammensetzen
return combine(smaller, current_state);
}
Manchmal erfolgt das „Zusammensetzen“ vor dem Aufruf, manchmal danach. Wichtig ist heute: der Schritt muss zur Basis führen.
Beispiel: Summe sum_to(n) — Schritt
int sum_to(int n) {
if (n == 0) return 0;
return n + sum_to(n - 1); // Schritt: n wird um 1 verkleinert
}
Hier ist die Verkleinerung offensichtlich: aus n wird n-1. Irgendwann wird n null erreichen und der Basisfall greift.
Beispiel: GGT (Euklidischer Algorithmus) — Schritt
Der GGT (gcd) ist ein gutes Beispiel, weil die Rekursion hier nicht nur über eine Zahl läuft, sondern über ein Paar. Basis: wenn b == 0, ist die Antwort a. Schritt: ersetze (a, b) durch (b, a % b).
int gcd(int a, int b) {
if (b == 0) return a; // Basis
return gcd(b, a % b); // Schritt: b wird durch den Rest kleiner
}
Warum führt das zur Basis? Weil a % b stets kleiner ist als b (sofern b != 0), also wird die zweite Zahl allmählich kleiner und irgendwann 0.
4. Prüfung der Konvergenz: erreichen wir die Basis?
Es ist sehr einfach, Rekursion zu schreiben, die elegant aussieht, aber in Wahrheit niemals stoppt. Deshalb ist es nützlich, sich vor dem Jubeln ein paar Kontrollfragen zu stellen. Sie klingen langweilig, sparen aber Stunden Debugging und einige Nerven.
Erstens, ist die Basis für alle zulässigen Eingabedaten erreichbar? Wenn du als Basis n == 0 wählst, der Benutzer aber -5 eingeben kann, wohin willst du dann verringern? In die negative Unendlichkeit? Keine besonders erfolgreiche Karriereplanung.
Zweitens, wird die Aufgabe bei jedem Schritt wirklich kleiner? Wenn du aus Versehen sum_to(n + 1) schreibst, rückt die Basis immer weiter weg, statt näher.
Drittens, ändert sich der Parameter überhaupt? Ein rekursiver Schritt wie return f(n); ist so gut wie eine Eintrittskarte zum Stack-Overflow.
Schauen wir uns zwei „schlechte“ Versionen an, um sie mit den Augen zu erkennen.
Schlechtes Beispiel: der Parameter ändert sich nicht
int sum_bad(int n) {
if (n == 0) return 0;
return n + sum_bad(n); // FEHLER: n wird nicht verkleinert
}
Das ist unendliche Rekursion. Die Basis existiert, aber niemand geht dorthin.
Schlechtes Beispiel: die Basis ist nicht erreichbar
int sum_bad2(int n) {
if (n == 0) return 0;
return n + sum_bad2(n + 1); // FEHLER: n wächst, die Basis rückt immer weiter weg
}
Wieder Unendlichkeit: die Basis „läuft weg“.
5. Warum ohne Basis das Programm „abstürzt“: der Stack ist nicht unendlich
Wenn eine rekursive Funktion sich selbst aufruft, passiert genau dasselbe wie bei jedem anderen Funktionsaufruf: ein neuer Stack-Frame wird angelegt. Wenn du die Basis vergessen hast (oder sie nicht erreichbar ist), erzeugst du immer wieder neue Frames, bis der Stack aufgebraucht ist. In diesem Moment beendet das Programm meist abrupt. Das ist ein Fall, in dem der Computer ehrlich versucht hat, deinen Befehl auszuführen, aber an die physikalischen Grenzen stößt: der Speicher für den Stack ist begrenzt.
Wichtig ist eine psychologische Falle zu verstehen: Rekursion „läuft“ nicht wie eine Endlosschleife while(true). In einer Schleife hast du einen Stack-Frame, und der Rumpf wird ewig ausgeführt. In Rekursion erzeugst du jedoch immer wieder neue Frames — viele, sehr viele — und das summiert sich.
Visualisierung: die unendliche Treppe der Aufrufe
Stellen wir uns so eine Funktion ohne Basis vor:
int boom(int n) {
return boom(n - 1); // keine Basis
}
Der Aufruf boom(3) führt zu einer Kette:
boom(3) ruft boom(2) auf
boom(2) ruft boom(1) auf
boom(1) ruft boom(0) auf
boom(0) ruft boom(-1) auf
...
Und so weiter, bis der Stack überläuft.
Mini-Demonstration: „Rekursion ohne Basis“
Nachfolgend ein Beispiel, das zwar kompiliert, aber logisch zum Scheitern verurteilt ist. Es ist nützlich als Illustration:
int factorial_bad(int n) {
// keine Basis -> unendliche Aufrufe
return n * factorial_bad(n - 1);
}
Selbst wenn du factorial_bad(1) aufrufst, wird die Funktion zu factorial_bad(0), dann zu factorial_bad(-1) und so weiter.
6. Praxis: Tracing und Mini-Anwendung
Wenn du Rekursion lernst, ist es oft hilfreich, die Aufrufe buchstäblich „durchzuspielen“. Ja, das ist wie ein Brettspiel „Call Stack: Studenten-Edition“, aber es zahlt sich aus. Wichtig ist, die zwei Phasen zu unterscheiden: was passiert vor dem Selbstaufruf und was passiert nach, wenn wir zurückkehren.
Mini-Tracing: wie Basis und Schritt zusammenwirken
Nehmen wir sum_to(3):
int sum_to(int n) {
if (n == 0) return 0;
return n + sum_to(n - 1);
}
Tracing:
sum_to(3) = 3 + sum_to(2)
sum_to(2) = 2 + sum_to(1)
sum_to(1) = 1 + sum_to(0)
sum_to(0) = 0 <-- Basis
dann Rückgaben:
sum_to(1) = 1 + 0 = 1
sum_to(2) = 2 + 1 = 3
sum_to(3) = 3 + 3 = 6
Wichtig ist: obwohl die Zeile return n + sum_to(n - 1); wie eine einzige Zeile aussieht, wird in Wirklichkeit zuerst sum_to(n - 1) berechnet, und erst dann + n ausgeführt.
Praktisches Beispiel: rekursive Befehle in einer Konsolenanwendung
Damit Rekursion nicht nur „eine Fakultät im Regal“ bleibt, packen wir sie als kleinen Befehlssatz in eine Anwendung. Wir machen keinen komplizierten String-Parser — ein einfaches Menü mit std::cin und ein paar Funktionen reichen. Ziel ist zu sehen, dass eine rekursive Funktion wie jede andere Funktion aussieht und auch so aufgerufen wird.
Rekursive Funktionen
long long factorial(int n) {
if (n == 0) return 1;
return n * factorial(n - 1);
}
int sum_to(int n) {
if (n == 0) return 0;
return n + sum_to(n - 1);
}
main: einfaches Menü
#include <iostream>
long long factorial(int n);
int sum_to(int n);
int main() {
int cmd = 0;
std::cin >> cmd;
if (cmd == 1) {
int n; std::cin >> n;
std::cout << factorial(n) << '\n'; // zum Beispiel: 120
} else if (cmd == 2) {
int n; std::cin >> n;
std::cout << sum_to(n) << '\n'; // zum Beispiel: 55
} else {
std::cout << "Unknown command\n"; // Unknown command
}
}
Hier ein wichtiger Gedanke: Rekursion ist kein „spezieller Modus von C++“. Es ist einfach eine Funktion, die sich selbst aufruft.
7. Typische Fehler
Fehler Nr. 1: „ich habe Rekursion geschrieben, aber den Basisfall vergessen“.
Das ist der häufigste Grund, warum Anfängerprogramme abstürzen. Der Code kann logisch aussehen und perfekt kompilieren, aber beim ersten Lauf in unendliche Aufrufe geraten und abrupt enden. Die Lösung ist simpel und unspektakulär: schreibe den Basisfall zuerst, noch bevor du den Schritt entwirfst.
Fehler Nr. 2: die Basis existiert, ist aber nicht erreichbar.
Klassische Situation: die Basis prüft n == 0, aber der Schritt macht n + 1 oder ändert n gar nicht. Formal ist die Basis vorhanden, aber es gibt keinen realen „Weg“ dorthin. Eine gute Gewohnheit ist, sich mental zu fragen: „in wie vielen Schritten komme ich sicher zur Basis?“ Wenn du keine Antwort hast, stimmt etwas nicht.
Fehler Nr. 3: falsche Basisantwort (z. B. factorial(0) = 0).
Manchmal ist die Basis gesetzt und der Schritt verkleinert die Aufgabe, die Rekursion endet, aber das Ergebnis ist falsch. Meist bedeutet das, dass die Basisantwort falsch gewählt wurde. Für Summen ist die Basis fast immer 0, für Produkte fast immer 1. Vertauscht man das, entstehen stille Fehler: das Programm stürzt nicht, aber liefert falsche Zahlen.
Fehler Nr. 4: der rekursive Schritt verkleinert die Aufgabe nicht in der richtigen Metrik.
Es kann sein, dass sich ein Parameter ändert, aber nicht garantiert, dass man sich der Basis nähert. Zum Beispiel reduzierst du n nicht um 1, sondern machst n = n - 2, vergisst aber, dass n ungerade sein kann und die Basis nur für n == 0 geprüft wird. Für n == 1 würde die Rekursion in negative Zahlen laufen. An solchen Stellen ist es wichtig, die zulässigen Eingabewerte und die Basis abzudecken.
Fehler Nr. 5: der rekursive Aufruf steht „am falschen Ort“ und du verstehst die Ausführungsreihenfolge nicht.
Die Zeile return n + f(n - 1); sieht simpel aus, wird aber in zwei Schritten berechnet: zuerst f(n - 1), dann das + mit n. Wenn du versuchst, währenddessen etwas zu drucken, kann leicht durcheinander geraten, wann genau std::cout ausgeführt wird. Tracing hilft: schreibe 3–4 Schritte von Aufrufen und Rückgaben auf und schau, wo du tatsächlich bist — vor dem Aufruf oder beim Zurückkehren.
GO TO FULL VERSION