# Rekursion: wenn sich eine Funktion selbst aufruft

> 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.

**Autor:** Mr. Benjamin · **Beruf:** IT-Grundlagen
**Veröffentlicht:** 2026-09-22 · **Aktualisiert:** 2026-09-22
**Quelle:** https://yellowbluetech.de/blog/rekursion-erklaert

---

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:

> **Merksatz**
>
> **Basisfall** (Abbruchbedingung): der einfachste Fall, der ohne weiteren Selbstaufruf beantwortet wird.
> **Rekursionsschritt**: die Funktion ruft sich mit einem **kleineren** Teilproblem selbst auf.
>
> Ohne Basisfall ruft sich die Funktion **endlos** auf – der Aufruf-Stack läuft über (*[Stack](/blog/datenstrukturen-grundlagen) Overflow*).

## Beispiel: Fakultät

Die Fakultät `n!` ist `n × (n-1) × … × 1`. Rekursiv formuliert: `n! = n × (n-1)!`, und `0! = 1` (Basisfall).

```text
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 = 24
```

Jeder 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 |

> **Prüfungstipp**
>
> Der Kernsatz, der geprüft wird: **Jede rekursive Funktion braucht einen Basisfall** – sonst Stack Overflow. Merke außerdem: **Jede Rekursion lässt sich auch als Schleife schreiben** und umgekehrt. Rekursion ist kein Muss, sondern eine Frage der Eleganz: Bei baumartigen Problemen (Ordnerstrukturen, Navigations­bäume) ist sie oft klarer, bei einfachen Zählschleifen ist die Iteration sparsamer.

## Wann lohnt sich Rekursion?

> **Hinweis**
>
> Immer dann, wenn das Problem selbst **rekursiv aufgebaut** ist: das Durchlaufen von Verzeichnisbäumen, das Verarbeiten verschachtelter Datenstrukturen oder klassische Teile-und-herrsche-Verfahren. Für einfache lineare Wiederholungen ist eine [Schleife](/blog/kontrollstrukturen-programmierung) meist die bessere Wahl, weil sie keinen zusätzlichen Speicher pro Schritt braucht. Wichtig bleibt in beiden Fällen: eine erreichbare Abbruchbedingung – bei der Rekursion der Basisfall, bei der Schleife die Abbruchbedingung.

## Selbstkontrolle

**Frage:** Was passiert mit einer rekursiven Funktion ohne Abbruchbedingung (Basisfall)?

- [ ] Sie liefert immer 0 zurück.
- [x] Sie ruft sich endlos auf, bis der Stack überläuft.
- [ ] Sie wird automatisch in eine Schleife umgewandelt.
- [ ] Nichts – der Compiler verhindert das.

**Erklärung:** Ohne Basisfall ruft sich die Funktion endlos selbst auf. Jeder Aufruf legt einen Eintrag auf den Aufruf-Stack, der irgendwann überläuft – das führt zum Stack Overflow und das Programm bricht ab.

## 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](/blog/sortier-suchalgorithmen) · [Programmablaufplan (PAP) und Struktogramm](/blog/algorithmus-struktogramm-pap)

## 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.