Ömer sagt:
Rekursion klingt verrückt, ist aber elegant: Eine Funktion ruft sich selbst auf, mit einem kleineren Problem. Das Wichtigste: der Basisfall – sonst läuft es ewig!
Was ist Rekursion?
1. Basisfall (Base Case)
Wann stoppt die Rekursion? Ohne Basisfall: Stack Overflow!
2. Rekursionsfall
Die Funktion ruft sich selbst mit einem kleineren Argument auf.
Fakultät – das klassische Beispiel
fakultaet.cC
int fakultaet(int n) { if (n == 0) return 1; // Basisfall return n * fakultaet(n-1); // Rekursionsfall }
Aufrufkette: fakultaet(4) = 24
f(4) → 4 × f(3)
f(3) → 3 × f(2)
f(2) → 2 × f(1)
f(1) → 1 × f(0)
f(0) = 1 ← Basisfall!
→ 1
→ 2
→ 6
→ 24
Aufbau einer rekursiven Funktion
| Bestandteil | Bedeutung | Bei Fakultät |
|---|---|---|
| Basisfall | Wann stoppt die Rekursion? | n == 0 → return 1 |
| Rekursionsfall | Wie wird das Problem kleiner? | n * fakultaet(n-1) |
| Aufrufkette | Wie baut sich der Stack auf? | f(4)→f(3)→f(2)→f(1)→f(0) |
Häufige Fehler
Warnung: Typische Rekursionsfehler
- Kein Basisfall: Die Funktion ruft sich endlos selbst auf → Stack Overflow (Absturz!). Jede rekursive Funktion braucht zwingend einen Basisfall.
- Basisfall nie erreicht: Die Bedingung ist falsch formuliert, sodass der Basisfall übersprungen wird. Beispiel:
fakultaet(-1)würde ewig rekursieren wenn keine Prüfung auf negative Zahlen vorhanden ist. - Zu tiefe Rekursion: Jeder Aufruf belegt Stack-Speicher. Bei sehr großen Eingaben (z.B.
fakultaet(100000)) ist das Stack-Limit schnell erreicht → Absturz.
sicher.cC
int fakultaet(int n) { if (n < 0) return -1; // Schutz vor negativen Zahlen if (n == 0) return 1; // Basisfall return n * fakultaet(n - 1); }
Wann Rekursion, wann Schleife?
| Rekursion | Schleife | |
|---|---|---|
| Lesbarkeit | Elegant für natürlich-rekursive Probleme | Klarer für einfache Wiederholungen |
| Performance | Langsamer (Stack-Overhead) | Schneller |
| Gefahr | Stack Overflow | Endlosschleife |
| Typisch | Baumstrukturen, Fibonacci, Quicksort | Alle anderen |
⚡ Code-Simulator
Schreibe eigene Funktionen und teste sie – der Simulator zeigt printf-Ausgaben:
C Simulator – Unit 20 – Funktionen
▶ Ausgabe
– Klicke AUSFÜHREN –
Ömer sagt:
Schreibe eigene Funktionen und ändere die Argumente beim Aufruf. So siehst du direkt wie Funktionen Daten verarbeiten!
🎯 Wissens-Quiz
Frage 1
Welche zwei Teile hat jede korrekte rekursive Funktion?
Frage 2
Was passiert ohne Basisfall bei einer rekursiven Funktion?
Frage 3
Was gibt fakultaet(0) zurück?
Frage 4
Was gibt fibonacci(5) zurück? (0,1,1,2,3,5,8...)
Frage 5
Ist Rekursion immer die beste Lösung?
Frage 6
Was ist zwingend notwendig damit Rekursion terminiert?
Frage 7
Was passiert wenn eine rekursive Funktion keinen Basisfall hat?
Frage 8
Was ist der Unterschied zwischen direkter und indirekter Rekursion?
📋 Spickzettel
Rekursion
BasisfallWann stoppen?
RekursionsfallSelbst aufrufen mit n-1
Basisfall = Pflicht!Sonst Stack Overflow
n! = n × (n-1)!Fakultät-Formel
Beispiele
fakultaet(n)n * fak(n-1)
fibonacci(n)fib(n-1)+fib(n-2)
summe(n)n + summe(n-1)
potenz(b,e)b * pot(b,e-1)
✅ Checkliste Unit 20
- Ich kann Basisfall und Rekursionsfall benennen
- Ich kann eine einfache rekursive Funktion schreiben
- Ich verstehe die Aufrufkette (Call Stack)
- Ich kenne die rekursive Fakultät und Fibonacci-Funktion