Eine Funktion ruft sich selbst auf und löst damit ein Problem Schritt für Schritt in kleineren Teilproblemen. Genau darin liegt die Stärke der Rekursion in der Informatik, aber auch ihre größte Falle: Ohne klaren Basisfall läuft der Prozess weiter, bis der Speicher versagt. Ich zeige, wie rekursive Algorithmen funktionieren, wann sie sinnvoll sind und warum Bäume, Verzeichnisse und Sortierverfahren ohne sie oft unnötig kompliziert würden.
Die wichtigsten Gedanken zur Rekursion auf einen Blick
- Rekursion bedeutet, dass sich eine Funktion selbst aufruft.
- Jede funktionierende Rekursion braucht einen Basisfall und einen Schritt, der dem Ende näherkommt.
- Der Aufrufstapel speichert jeden offenen Funktionsaufruf und benötigt dafür zusätzlichen Speicher.
- Für Baumstrukturen und verschachtelte Daten ist Rekursion oft besonders übersichtlich.
- Eine Schleife ist häufig effizienter, wenn nur ein einfacher Zähler oder eine lineare Folge verarbeitet wird.
Was Rekursion in der Informatik wirklich bedeutet
Rekursion liegt vor, wenn eine Funktion ihre eigene Definition erneut verwendet. Das klingt zunächst nach einem logischen Kreis. Praktisch wird ein großes Problem jedoch auf eine kleinere Version desselben Problems zurückgeführt, bis ein direkt lösbarer Fall erreicht ist.
Eine rekursive Funktion besteht deshalb immer aus zwei Teilen. Der Basisfall beendet die Aufrufe, während der rekursive Fall die Funktion mit einem veränderten Eingangswert erneut startet.
funktion fakultaet(n)
wenn n <= 1
gib 1 zurück
sonst
gib n * fakultaet(n - 1) zurückBei fakultaet(4) entsteht die Folge 4 · 3 · 2 · 1. Entscheidend ist nicht der Selbstaufruf allein, sondern dass sich der Parameter bei jedem Schritt der Abbruchbedingung nähert. Genau diese Bewegung macht aus einer möglichen Endlosschleife einen terminierenden Algorithmus.
So läuft ein rekursiver Aufruf im Speicher ab
Der Computer führt die Aufrufe nicht einfach übereinander aus, sondern legt für jeden Aufruf einen Eintrag auf dem Call Stack, dem Aufrufstapel, ab. Dort stehen unter anderem Parameter, lokale Variablen und die Rücksprungadresse.
Bei fakultaet(4) wartet der erste Aufruf, während fakultaet(3), fakultaet(2) und fakultaet(1) gestartet werden. Erst wenn der Basisfall den Wert 1 liefert, werden die offenen Aufrufe in umgekehrter Reihenfolge abgeschlossen.
fakultaet(4)
fakultaet(3)
fakultaet(2)
fakultaet(1) = 1
= 2
= 6
= 24In der Praxis achte ich deshalb zuerst auf die maximale Rekursionstiefe. Eine Funktion kann logisch korrekt sein und trotzdem mit einem Stack Overflow scheitern, wenn die Eingabe zu groß wird oder die Aufruftiefe unkontrolliert wächst.
Anschauliche Beispiele aus der Programmierung
Verzeichnisse und verschachtelte Strukturen
Ein Dateisystem besteht aus Ordnern, die weitere Ordner enthalten können. Eine Funktion kann jeden Ordner ausgeben, Dateien verarbeiten und sich für jeden Unterordner erneut aufrufen. Die Struktur des Problems und die Struktur des Codes passen hier fast perfekt zusammen.
funktion durchsuche(ordner)
für jedes element in ordner
wenn element ein unterordner ist
durchsuche(element)
sonst
verarbeite(element)Das Beispiel zeigt, warum Rekursion bei unbekannter Verschachtelungstiefe angenehm ist. Eine Schleife müsste meist mit einer zusätzlichen Datenstruktur wie einer Warteschlange oder einem eigenen Stack arbeiten.
Binäre Bäume
Bei einem binären Suchbaum besitzt jeder Knoten höchstens zwei Nachfolger. Eine Suche kann den aktuellen Knoten prüfen und danach nur im linken oder rechten Teilbaum weitermachen. Der Algorithmus wird dadurch kompakt, weil ein Teilbaum wieder genau wie ein vollständiger Baum behandelt werden kann.
Die Laufzeit hängt von der Form des Baums ab. In einem gut ausgeglichenen Baum benötigt die Suche ungefähr O(log n) Schritte, in einem stark schiefen Baum kann sie im ungünstigsten Fall auf O(n) anwachsen.
Teile und herrsche
Viele Algorithmen teilen ein Problem, lösen die Teilprobleme rekursiv und setzen die Ergebnisse wieder zusammen. Dieses Muster heißt Divide and Conquer und wird beispielsweise bei Mergesort oder Quicksort verwendet.
Bei Mergesort wird eine Liste immer wieder halbiert. Danach werden die sortierten Hälften zusammengeführt. Die Rekursion endet, sobald ein Teil nur noch ein Element enthält, denn eine einteilige Liste ist bereits sortiert.
Mathematische Folgen
Die Fakultät eignet sich zum Lernen, ist aber kein besonders überzeugender Produktionsfall. Bei der Fibonacci-Folge wird das Problem sichtbarer, weil die einfache rekursive Variante viele Werte mehrfach berechnet.
funktion fibonacci(n)
wenn n <= 1
gib n zurück
sonst
gib fibonacci(n - 1) + fibonacci(n - 2) zurückDiese naive Lösung wächst sehr schnell und wird bereits bei mittelgroßen Werten langsam. Mit Memoisierung, also dem Zwischenspeichern bereits berechneter Ergebnisse, lässt sich die Laufzeit deutlich reduzieren. Für eine lineare Folge ist eine Schleife trotzdem meist die klarere und speichersparendere Wahl.
Rekursion oder Schleife
Rekursion und Iteration können oft dasselbe Ergebnis liefern. Die Entscheidung sollte nicht nach dem Motto „rekursiv ist eleganter“ fallen, sondern danach, welche Form die Daten und die Aufgabe besser abbildet.
| Kriterium | Rekursion | Iteration mit Schleife |
|---|---|---|
| Lesbarkeit | Sehr gut bei Bäumen und verschachtelten Strukturen | Sehr gut bei einfachen Wiederholungen |
| Speicherbedarf | Zusätzlicher Speicher pro Aufruf | Oft konstanter Speicherbedarf |
| Fehlerrisiko | Basisfall oder Fortschritt können fehlen | Schleifenbedingung kann fehlerhaft sein |
| Typische Verwendung | Bäume, Backtracking, Teile-und-herrsche | Zähler, Listen, fortlaufende Berechnungen |
Bei einer einfachen Summe von 1 bis 1.000 würde ich eine Schleife bevorzugen. Bei einer Baumtraversierung wirkt eine rekursive Lösung dagegen oft natürlicher und lässt sich leichter prüfen. Eleganter Code ist aber nicht automatisch schneller, weil jeder rekursive Aufruf Verwaltungsaufwand erzeugt.
Manche Compiler und Programmiersprachen können bestimmte Endrekursionen optimieren. Darauf sollte man sich jedoch nicht blind verlassen. Besonders in Python bleibt jeder Aufruf auf dem Stapel, während die maximale Rekursionstiefe zusätzlich begrenzt ist.
Die häufigsten Fehler beim Schreiben rekursiver Funktionen
Der Basisfall fehlt
Ohne Basisfall ruft sich die Funktion immer weiter auf. Das Ergebnis ist keine besonders tiefe Lösung, sondern meist ein Stack Overflow oder eine vom System erzwungene Abbruchmeldung.
Der Eingangswert wird nicht kleiner
Ein Basisfall allein reicht nicht. Der rekursive Aufruf muss ihn auch erreichen können. Wenn statt n - 1 versehentlich wieder n übergeben wird, verändert sich das Problem nicht und die Funktion steckt fest.
Zu viele Teilprobleme werden doppelt gelöst
Das Fibonacci-Beispiel zeigt diesen Fehler besonders deutlich. Wer dieselben Teilwerte immer wieder berechnet, verschwendet Zeit. Memoisierung oder eine iterative Lösung beseitigt diese Doppelarbeit.
Die Rückgabewerte werden falsch kombiniert
Eine rekursive Funktion muss nicht nur weiterlaufen, sondern die Ergebnisse der Rückkehr korrekt verwenden. Bei der Fakultät wird multipliziert, beim Durchsuchen eines Baums werden Ergebnisse eventuell gesammelt. Ein fehlender Rückgabewert kann die gesamte Berechnung unbemerkt in einen falschen Zustand bringen.
Lesen Sie auch: Schutzziele der Informationssicherheit verständlich erklärt
Die Rekursionstiefe wird unterschätzt
Bei sehr tiefen Listen, großen Verzeichnisbäumen oder langen Zeichenketten kann der Speicher zum begrenzenden Faktor werden. Ich teste deshalb nicht nur den kleinen Beispielwert, sondern auch leere Eingaben, Grenzwerte und ungewöhnlich tiefe Strukturen.
Wo Rekursion besonders gut passt
Die Methode ist stark, wenn ein Problem eine natürliche Hierarchie besitzt. Dazu gehören Syntaxbäume von Programmiersprachen, HTML-Strukturen, mathematische Ausdrücke, Spielbäume und Suchverfahren mit Rücksprung.
Beim Backtracking probiert ein Algorithmus eine Möglichkeit aus, geht bei einem Konflikt zurück und versucht die nächste. Sudoku-Löser, Labyrinthsuche und manche Varianten des Rucksackproblems folgen diesem Muster. Die Rekursion speichert dabei implizit, an welcher Stelle die vorige Entscheidung wieder aufgenommen werden muss.
Auch bei der Verarbeitung historischer Dokumente kann eine Baumstruktur entstehen, etwa wenn Sammlungen, Kategorien und einzelne Datensätze verschachtelt organisiert sind. Hier zeigt sich eine schöne Verbindung zwischen alter Ordnungstechnik und moderner Informatik: Die Maschine arbeitet nicht nur mit einzelnen Einträgen, sondern mit Beziehungen zwischen Ebenen.
Weniger passend ist Rekursion bei sehr großen linearen Datenmengen, wenn die Aufgabe nur aus einer einfachen Wiederholung besteht. Dann sind Schleifen, Streams oder spezielle Bibliotheksfunktionen oft robuster und benötigen weniger Speicher.
Wie man Rekursion systematisch versteht und testet
Ich beginne bei jeder rekursiven Aufgabe mit dem kleinsten sinnvollen Fall. Danach formuliere ich genau, wie aus einem Problem der Größe n ein kleineres Problem entsteht und wie die Ergebnisse wieder zusammenfinden.
- Bestimme den Basisfall, der direkt gelöst werden kann.
- Definiere den rekursiven Schritt mit einer nachweisbar kleineren Eingabe.
- Prüfe, wie viele Aufrufe maximal gleichzeitig offen bleiben.
- Teste zuerst leere, minimale und danach ungewöhnlich große Eingaben.
- Vergleiche Laufzeit und Speicherbedarf mit einer iterativen Variante.
Beim Debuggen hilft es, jeden Aufruf mit seinem Parameter zu protokollieren. So wird schnell sichtbar, ob sich der Wert tatsächlich verändert oder ob ein Teilproblem mehrfach und unnötig bearbeitet wird. Für komplexe Abläufe zeichne ich außerdem gern den Aufrufbaum, weil Fehler darin viel früher auffallen als in einer langen Codezeile.
Die beste Faustregel für den Einsatz
Rekursion ist kein Selbstzweck und auch kein Qualitätsmerkmal für sich. Sie ist dann die richtige Wahl, wenn sich die Aufgabe als verschachtelte Struktur oder als wiederkehrendes Teilproblem beschreiben lässt und die Rekursionstiefe beherrschbar bleibt.
Für Anfänger ist die Fakultät ein guter Einstieg, für die Praxis sind Verzeichnisse, Bäume und Divide-and-Conquer-Algorithmen lehrreicher. Wer immer zuerst den Basisfall, den Fortschritt und den Speicherbedarf prüft, vermeidet die drei größten Fallen und erkennt schnell, wann eine Schleife die bessere Lösung ist.
