Rekursion verstehen

Bisher haben wir gesehen, wie man mit Schleifen einen Vorgang wiederholt. Es gibt aber eine zweite, oft elegantere Methode der Wiederholung: Rekursion. Eine Funktion, die sich selbst aufruft. Klingt zunächst paradox – wie kann eine Funktion fertig werden, wenn sie zwischendurch nochmal anfängt? Doch genau dieses Prinzip löst manche Probleme erstaunlich elegant und kompakt.

Rekursion ist berüchtigt dafür, am Anfang das Gehirn zu verknoten. Aber wer einmal den „Klick" hat, sieht überall rekursive Strukturen: in Datenstrukturen wie Bäumen, in Algorithmen wie Merge Sort, in Datei-Systemen mit Unter-Unter-Verzeichnissen. Diese Lektion bringt dir das Konzept Schritt für Schritt nahe.

1) Die zentrale Idee – ein Problem zerlegen

Rekursion bedeutet, ein Problem zu lösen, indem man eine kleinere Version desselben Problems löst und das Ergebnis mit etwas Lokalem kombiniert. Klassische Analogie: russische Matrjoschka-Puppen. Die größte Puppe enthält eine kleinere, die wieder eine kleinere, und so weiter – bis ganz innen die kleinste, nicht mehr teilbare Puppe steht.

2) Die zwei Bestandteile jeder Rekursion

Jede rekursive Funktion braucht zwingend zwei Bestandteile, sonst funktioniert sie nicht. Diese sind die zentralen Bausteine, die du in jeder Klausur-Aufgabe erkennen musst:

• Basisfall (Abbruchbedingung): der einfachste Fall, in dem die Funktion ohne weiteren Selbstaufruf ein Ergebnis liefert. Hier endet die Rekursion. Ohne Basisfall: Endlos-Rekursion und Programmabsturz.
• Rekursionsschritt: die Funktion ruft sich selbst auf, aber mit einem einfacheren Argument – das näher am Basisfall liegt. Das eigene Ergebnis wird mit dem Rückgabewert kombiniert.

Anders gesagt: jede Rekursion muss sich systematisch auf den Basisfall zubewegen, sonst hört sie nie auf. Das verletzt die Terminiertheit – und ist damit kein gültiger Algorithmus mehr.

3) Klassiker: die Fakultät

Die Fakultät einer natürlichen Zahl n ist das Produkt aller Zahlen von 1 bis n. Also 5! = 5 · 4 · 3 · 2 · 1 = 120. Mathematisch ist die Fakultät bereits rekursiv definiert: n! = n · (n-1)!, und 0! = 1. Diese Definition lässt sich eins zu eins in Code übersetzen:

4) Der Call-Stack – wie der Computer Rekursion verwaltet

Aber wie geht das technisch? Wie kann eine Funktion sich selbst aufrufen, ohne dass alles durcheinander gerät? Der Trick: jeder Funktionsaufruf bekommt seinen eigenen Speicherbereich mit eigenen Variablen, dem sogenannten Stack-Frame. Diese werden auf einem Stack verwaltet (mehr dazu in Lektion 9).

Beim Aufruf wird ein neuer Frame oben drauf gelegt (push), beim Rückkehr wieder runter (pop). Das LIFO-Prinzip („Last In, First Out"): zuletzt aufgerufen, zuerst beendet. Schau dir das live an:

5) Stack Overflow – die Grenzen der Rekursion

Der Call-Stack hat eine begrenzte Größe (je nach System meist einige Tausend bis Millionen Frames). Wenn eine Rekursion zu tief geht – etwa weil der Basisfall nie erreicht wird – läuft der Stack über. Das Programm crasht mit einem Stack Overflow Error. Davon hat übrigens die berühmte Website ihren Namen.

Typische Ursachen:

• Basisfall vergessen: die Rekursion bricht nie ab. Klassischer Anfängerfehler.
• Basisfall wird nie erreicht: der Rekursionsschritt bewegt sich nicht auf den Basisfall zu (z.B. fakultaet(n + 1) statt n - 1).
• Problem ist zu groß: auch eine korrekte Rekursion kann bei riesigen Eingaben den Stack sprengen. Beispiel: eine Verzeichnis-Rekursion in einem Baum mit Millionen Ebenen.

6) Klassische rekursive Beispiele

Welche Probleme lassen sich gut rekursiv lösen? Vor allem solche, die selbstähnliche Struktur haben. Hier die wichtigsten Klassiker, die in jeder Algorithmen-Vorlesung auftauchen:

7) Der Rekursionsbaum – Aufrufe visualisieren

Bei Funktionen, die sich mehrfach selbst aufrufen (wie Fibonacci), bekommen wir keine lineare Aufrufkette mehr, sondern einen Rekursionsbaum. Jeder Aufruf verzweigt sich in mehrere Kinder. Schau dir fib(5) an:

8) Iterativ vs. rekursiv – wann was?

Praktisch jede rekursive Funktion lässt sich auch iterativ (mit Schleifen) lösen, und umgekehrt. Welche Variante ist besser? Hängt vom Problem ab. Schau dir Fakultät in beiden Versionen an:

9) Häufige Fehler bei Rekursion

Rekursion hat ihre Tücken. Diese vier Fehler kommen in IHK-Klausuren immer wieder vor:

• Basisfall fehlt: die Rekursion bricht nie ab → Stack Overflow. Immer als ersten Schritt im Code den Basisfall schreiben, dann den Rekursionsschritt.
• Falsche Reduktion: der Rekursionsschritt bewegt sich nicht auf den Basisfall zu. Klassiker: fak(n + 1) statt fak(n - 1). Auch hier: Endlosrekursion.
• Rückgabewert vergessen: der Selbstaufruf wird gemacht, aber sein Ergebnis nicht weiterverwendet. fak(n - 1) alleine bringt nichts – es muss GIB ZURÜCK n * fak(n - 1) heißen.
• Globale Variablen verwenden: bei Rekursion soll jeder Aufruf seine eigenen lokalen Variablen haben. Wer eine globale Variable im Selbstaufruf ändert, bekommt verwirrendes Verhalten.

10) Wo begegnet dir Rekursion in der echten Welt?

Auch wenn du selten von Hand eine rekursive Funktion programmierst – das Konzept steckt überall in der Software, die du täglich nutzt:

• Datei-Systeme: ein Ordner enthält Dateien und Unter-Ordner, die wieder Ordner und Dateien enthalten. Ein find-Befehl oder das Durchlaufen eines Verzeichnisbaums ist klassisch rekursiv.
• JSON/XML-Parser: ein JSON-Objekt kann andere Objekte enthalten, die wieder Objekte enthalten. Parser arbeiten rekursiv.
• Web-Crawler: eine Webseite enthält Links zu weiteren Seiten, die wieder Links enthalten. Suchmaschinen-Crawler arbeiten rekursiv.
• Compiler: Syntax-Bäume werden rekursiv aufgebaut und ausgewertet. Ein Ausdruck wie (a + b) * c hat eine rekursive Struktur.
• Bildbearbeitung – Eimer-Werkzeug: „fülle die Fläche mit Farbe" geht klassisch rekursiv durch die Nachbarpixel.
• Fraktale: mathematische Figuren wie das Sierpinski-Dreieck oder der Mandelbrot-Mengen leben von rekursiver Definition.

Zusammenfassung

Rekursion ist eine Funktion, die sich selbst aufruft – als Alternative zu Schleifen. Sie eignet sich, wenn ein Problem auf eine kleinere Version desselben Problems reduziert werden kann. Jede rekursive Funktion braucht zwei Bestandteile: einen Basisfall (Abbruchbedingung, liefert ohne Selbstaufruf ein Ergebnis) und einen Rekursionsschritt (Selbstaufruf mit kleinerem Argument, das sich auf den Basisfall zu bewegt). Technisch verwaltet der Computer Rekursion über den Call-Stack – ein Stack von Stack-Frames, jeder mit eigenen Variablen. Wenn der Stack überläuft: Stack Overflow Error – meist durch fehlenden oder unerreichbaren Basisfall. Klassische Beispiele: Fakultät, Fibonacci (Achtung: exponentielle Komplexität), Türme von Hanoi, Baum-Traversal. Bei mehrfachen Selbstaufrufen entsteht ein Rekursionsbaum – nützlich zur Analyse der Komplexität (siehe O-Notation in L8). Iterativ vs. rekursiv: beides oft möglich, beides liefert dasselbe Ergebnis. Iterativ meist schneller und speicher-effizienter, rekursiv oft eleganter bei natürlich rekursiven Problemen. Stolperfallen: fehlender Basisfall, falsche Reduktion, vergessener Rückgabewert, globale Variablen. In der Praxis begegnet dir Rekursion in Datei-Systemen, JSON-Parsern, Compilern, Web-Crawlern, Bildbearbeitung und Fraktalen. Nächste Lektion: konkrete Algorithmen mit Anwendung dieser Konzepte – Suchen: linear vs. binär.