Rekursion: wenn sich eine Funktion selbst aufruft
Kurzantwort
Rekursion bedeutet, dass eine Funktion sich selbst aufruft, um ein Problem in kleinere Teilprobleme zu zerlegen. Jede rekursive Funktion braucht eine Abbruchbedingung (den Basisfall), sonst ruft sie sich endlos auf und der Aufruf-Stack läuft über. Rekursion ist elegant für Probleme, die selbst rekursiv aufgebaut sind, etwa Baumstrukturen – kostet aber Speicher für jeden verschachtelten Aufruf.
Teil des Lernpfads Programmieren und Softwareentwicklung · Schritt 8 von 18
Eine Funktion, die sich selbst aufruft? Das klingt nach einem Fehler, ist aber ein mächtiges Werkzeug. Rekursion löst Probleme, indem sie sie in kleinere, gleichartige Teilprobleme zerlegt – bis ein einfachster Fall erreicht ist.
Das Grundprinzip
Eine rekursive Funktion besteht immer aus zwei Teilen:
Beispiel: Fakultät
Die Fakultät n! ist n × (n-1) × … × 1. Rekursiv formuliert: n! = n × (n-1)!, und 0! = 1 (Basisfall).
funktion fakultaet(n):
wenn n <= 1: // Basisfall
gib 1 zurück
sonst: // Rekursionsschritt
gib n * fakultaet(n - 1)
fakultaet(4)
= 4 * fakultaet(3)
= 4 * 3 * fakultaet(2)
= 4 * 3 * 2 * fakultaet(1)
= 4 * 3 * 2 * 1 = 24Jeder Aufruf wartet auf das Ergebnis des nächsten, bis der Basisfall die Kette „auflöst".
Rekursion vs. Schleife
| Rekursion | Schleife (Iteration) | |
|---|---|---|
| Idee | Funktion ruft sich selbst | wiederholter Durchlauf |
| Speicher | ein Stack-Eintrag pro Aufruf | konstant |
| Lesbarkeit | elegant bei verschachtelten Strukturen | einfach bei linearen Abläufen |
| Risiko | Stack Overflow ohne Basisfall | Endlosschleife ohne Abbruch |
Wann lohnt sich Rekursion?
Selbstkontrolle
Selbstkontrolle
Was passiert mit einer rekursiven Funktion ohne Abbruchbedingung (Basisfall)?
Häufige Fragen
Ist Rekursion langsamer als eine Schleife?
Oft ja, weil jeder Selbstaufruf Verwaltungsaufwand und Speicher auf dem Aufruf-Stack kostet. Für dieselbe Aufgabe ist eine Schleife meist sparsamer. Der Vorteil der Rekursion liegt nicht in der Geschwindigkeit, sondern in der Klarheit bei passenden Problemen.
Was ist ein Stack Overflow?
Jeder Funktionsaufruf legt seine Daten auf den Aufruf-Stack. Ruft sich eine Funktion zu oft (oder endlos) selbst auf, ist der Stack-Speicher irgendwann erschöpft und das Programm bricht mit einem Stack Overflow ab. Ein korrekter Basisfall, der nah genug erreichbar ist, verhindert das.
Kann man jede Schleife durch Rekursion ersetzen?
Grundsätzlich ja, und umgekehrt lässt sich jede Rekursion in eine Schleife umschreiben. Beide sind gleich mächtig. Welche Variante besser ist, hängt vom Problem ab: baumartige Strukturen sprechen für Rekursion, einfache lineare Wiederholungen für Schleifen.
Was ist der Basisfall genau?
Der Basisfall ist die Situation, in der die Funktion ein Ergebnis direkt zurückgibt, ohne sich noch einmal selbst aufzurufen. Er beendet die Rekursion. Bei der Fakultät ist das n gleich 0 oder 1 mit dem Ergebnis 1. Jeder Rekursionsschritt muss sich diesem Basisfall annähern.
Weiterlesen: Sortier- und Suchalgorithmen verstehen · Programmablaufplan (PAP) und Struktogramm
Das Wichtigste in Kürze
- Rekursion: eine Funktion ruft sich selbst mit einem kleineren Teilproblem auf.
- Pflicht: der Basisfall (Abbruchbedingung) – sonst Stack Overflow.
- Standardbeispiel: die Fakultät (
n! = n × (n-1)!,0! = 1). - Rekursion ↔ Schleife: beide gleich mächtig, ineinander überführbar.
- Rekursion glänzt bei baumartigen Problemen, Schleifen bei linearen.