Mit Google fortfahren
Rekursion in der Informatik einfach erklärt
Bei einer Rekursion ruft eine Funktion sich selbst mit einer einfacheren Eingabe auf. Das funktioniert nur, wenn sie dabei einen erreichbaren Basisfall ansteuert. Danach werden die offenen Aufrufe in umgekehrter Reihenfolge abgeschlossen.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Woran erkennst du eine funktionierende Rekursion?
Stell dir eine Matroschka vor: Jede Puppe enthält eine kleinere Puppe derselben Art. Bei der kleinsten Puppe endet die Verschachtelung. Eine informatische Rekursion braucht ebenfalls eine kleinere Variante und ein festgelegtes Ende.
Basisfall
Der Basisfall ist eine Eingabe, deren Ergebnis ohne weiteren Selbstaufruf feststeht. Er beendet den rekursiven Abstieg.
Eine vollständige Rekursion besitzt vier Bestandteile:
- Basisfall: Ein einfacher Fall wird direkt gelöst.
- Rekursiver Schritt: Die Funktion ruft sich selbst auf.
- Verkleinerung: Die neue Eingabe liegt näher am Basisfall.
- Rückführung: Aus dem Ergebnis des kleineren Problems entsteht das Ergebnis des ursprünglichen Problems.
Die Summe von 0 bis n lässt sich so beschreiben:
summe(0)liefert0.- Für
n > 0gilt:summe(n)liefertsumme(n - 1) + n.
Der Aufruf wird mit jedem Schritt kleiner. Deshalb erreicht er bei einer nichtnegativen ganzen Zahl schließlich summe(0).
Ein Selbstaufruf allein ist noch keine brauchbare Rekursion. Entscheidend sind ein erreichbarer Basisfall und ein Schritt, der sicher dorthin führt.
Wie laufen Aufrufe und Rückgaben ab?
Jeder noch nicht abgeschlossene Funktionsaufruf wird auf dem Aufrufstapel, auch Stack genannt, vorgemerkt. Dort liegen unter anderem seine Parameter, lokalen Variablen und die Stelle, an der es nach dem Selbstaufruf weitergeht.
Ein neuer Aufruf kommt oben auf den Stapel. Sobald der Basisfall erreicht ist, kehren die Aufrufe in umgekehrter Reihenfolge zurück: Der zuletzt begonnene Aufruf endet zuerst.
Für nichtnegative ganze Zahlen kann die Fakultät so definiert werden:
fakultaet(0)undfakultaet(1)liefern1.- Für
n > 1liefertfakultaet(n)den Wertn · fakultaet(n - 1).
Bei fakultaet(4) entsteht zunächst der Abstieg:
fakultaet(4) → fakultaet(3) → fakultaet(2) → fakultaet(1)
Nun liefert der Basisfall 1. Beim Rücklauf werden die wartenden Multiplikationen ausgeführt:
fakultaet(1) = 1fakultaet(2) = 2 · 1 = 2fakultaet(3) = 3 · 2 = 6fakultaet(4) = 4 · 6 = 24
Damit gilt: 4! = 4 · 3 · 2 · 1 = 24.
Wähle in jeder Lücke die passende Form und prüfe anschließend deine Antworten.
Beim rekursiven entstehen neue Aufrufe. Der direkt lösbare Fall heißt . Offene Aufrufe liegen auf dem . Beim werden ihre Ergebnisse in umgekehrter Reihenfolge verarbeitet.
Wie prüfst du, ob die Rekursion sicher endet?
Eine Abbruchbedingung prüft, ob der Basisfall erreicht ist. Das genügt aber nur, wenn die rekursiven Aufrufe tatsächlich auf diesen Fall zulaufen.
Prüfe eine Rekursion deshalb mit drei Fragen:
- Für welche Eingabe wird kein weiterer Selbstaufruf ausgeführt?
- Welche Größe verändert sich bei jedem Aufruf?
- Warum erreicht diese Größe den Basisfall nach endlich vielen Schritten?
Betrachte die Idee herunter(n):
- Falls
n == 0, endet die Funktion. - Andernfalls ruft sie
herunter(n + 1)auf.
Obwohl ein Basisfall vorhanden ist, endet der Aufruf herunter(3) nicht: Die Werte 3, 4, 5, ... entfernen sich von 0.
Mit herunter(n - 1) würde sich eine positive ganze Zahl dagegen bei jedem Schritt dem Basisfall 0 nähern.
Eine sehr tiefe Rekursion kann den verfügbaren Speicher des Aufrufstapels überschreiten. Das führt zu einem Stackoverflow. Neben der logischen Terminierung musst du deshalb auch die mögliche Rekursionstiefe beachten.
Wann ist Rekursion besser als Iteration?
Iteration wiederholt Anweisungen mit einer Schleife. Rekursion erzeugt dagegen verschachtelte Funktionsaufrufe. Viele Aufgaben lassen sich auf beide Arten lösen.
Rekursion ist besonders naheliegend, wenn das Problem selbst aus gleichartigen kleineren Teilen besteht, etwa bei Listen, Bäumen, Teile-und-herrsche-Verfahren oder Backtracking.
Iteration ist oft günstiger, wenn eine einfache Schleife denselben Zusammenhang klar ausdrückt. Sie benötigt gewöhnlich keinen zusätzlichen Stapelspeicher für viele offene Funktionsaufrufe.
Die Fakultät lässt sich leicht iterativ berechnen: Beginne mit dem Produkt 1 und multipliziere nacheinander mit 1, 2, ..., n.
Die rekursive Variante zeigt das Prinzip gut, bietet für diese Aufgabe aber keinen offensichtlichen Vorteil gegenüber der Schleife. Für 5 liefern beide Verfahren 5! = 120.
Vertiefung: Mehrfachberechnungen im Aufrufbaum
Die Fibonacci-Folge beginnt mit fib(0) = 0 und fib(1) = 1. Danach gilt für n > 1:
fib(n) = fib(n - 1) + fib(n - 2)
Die direkte rekursive Umsetzung verzweigt bei fast jedem Aufruf. Für fib(5) entstehen insgesamt 15 Funktionsaufrufe. Werte wie fib(3) und fib(2) werden mehrfach berechnet.
Das Speichern bereits berechneter Ergebnisse heißt Memoisation. Es verhindert solche Wiederholungen. Eine iterative Lösung kann die benötigten Werte stattdessen schrittweise von unten nach oben aufbauen.
Wähle Rekursion nicht nur, weil der Code kurz aussieht. Prüfe auch Verständlichkeit, wiederholte Berechnungen, Stapelspeicher und maximale Tiefe.
Wo zeigt Rekursion ihre Stärke?
Türme von Hanoi
Beim Spiel „Türme von Hanoi“ soll ein Turm aus verschieden großen Scheiben auf eine andere Stange gelangen. Pro Zug darfst du nur eine Scheibe bewegen, und eine größere Scheibe darf nie auf einer kleineren liegen.
Um n Scheiben zu bewegen:
- Bewege die oberen
n - 1Scheiben auf die Hilfsstange. - Bewege die größte Scheibe auf die Zielstange.
- Bewege die
n - 1Scheiben von der Hilfsstange auf die Zielstange.
Der Basisfall ist eine einzelne Scheibe. Für n Scheiben sind 2^n - 1 Züge nötig; bei drei Scheiben also 2^3 - 1 = 7 Züge.
Rekursive Datenstrukturen
Eine Liste ist entweder leer oder besteht aus einem ersten Element und einer restlichen Liste. Ein binärer Baum ist entweder leer oder besteht aus einem Knoten sowie einem linken und einem rechten Teilbaum.
Diese Strukturen legen rekursive Verarbeitung nahe: Bearbeite einen Teil und wende dasselbe Verfahren auf die verbleibende Liste oder die Teilbäume an.
Teile und Herrsche sowie Backtracking
Bei Teile und Herrsche wird ein Problem in einfachere Teilprobleme zerlegt. Deren Lösungen werden anschließend zusammengesetzt. Mergesort folgt diesem Muster, indem es Folgen teilt, die Hälften sortiert und wieder verschmilzt.
Beim Backtracking wird eine Möglichkeit ausprobiert. Führt sie in eine Sackgasse, wird der letzte Schritt zurückgenommen und die nächste Möglichkeit getestet. Das N-Damenproblem ist ein typisches Beispiel.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Rekursion
- Aufbau
- Basisfall
- rekursiver Schritt
- Annäherung an den Basisfall
- Rückführung
- Ablauf
- Abstieg mit neuen Aufrufen
- Speicherung auf dem Aufrufstapel
- Rücklauf in umgekehrter Reihenfolge
- Beurteilung
- Terminierung
- Rekursionstiefe
- Mehrfachberechnungen
- Vergleich mit Iteration
- Anwendungen
- Listen und Bäume
- Teile und Herrsche
- Türme von Hanoi
- Backtracking
- Aufbau
Abschluss-Check
Du beherrschst das Grundprinzip, wenn du bei einer rekursiven Funktion den Basisfall, den verkleinernden Schritt und die Rückführung zeigen sowie ihr Ende begründen kannst.