Rekursion und Iteration: Algorithmen, die sich selbst aufrufen

Rekursion und Iteration: Algorithmen, die sich selbst aufrufen

https://bildung.social/@oerinformatik/

https://oer-informatik.de/rekursion

Rekursion, Iteration, Abbruchbedingung, Aufrufstapel, Stapelüberlauf, Schreibtischtest, Endrekursion, Teile und herrsche, Memoisation, Pseudocode

tl/dr; (ca. 22 min Lesezeit): Eine rekursive Funktion löst ein Problem, indem sie sich selbst mit einem kleineren Teilproblem aufruft, bis eine Abbruchbedingung erreicht ist. Der Artikel erklärt Abbruchbedingung und Rekursionsschritt, den Aufrufstapel, den Unterschied zwischen Abstieg und Aufstieg, den Schreibtischtest rekursiver Algorithmen und die typischen Fehler. Er zeigt, wie Du Rekursion in Iteration umwandelst und umgekehrt, wann sich welche Lösung lohnt und wie Bäume, Teile-und-herrsche-Verfahren und Endrekursion funktionieren [AI-Assisted]. (Zuletzt geändert am 27.10.2026)

Dieser Artikel ist Teil einer Artikelreihe über Algorithmen und Programmentwurf: Algorithmen mit Pseudocode dokumentieren / Prozedurale Algorithmen mit Arrays / Sortieralgorithmen und Vergleichsfunktionen / Rekursion und Iteration / Übungsaufgaben zu Rekursion und Iteration

Schon fit in diesem Thema? Nutze die Kann-Liste und die Leitfragen unter dem Artikel als Checkliste, ob Du die relevanten Kompetenzen bereits hast. Hier klicken, um Kann-Liste ein- oder auszublenden

Im Fahrrad-Onlineshop liegt der Artikel „Long John“ in der Kategorie „Long John“, die zu „E-Lastenräder“ gehört, die zu „Lastenräder“ gehört, die zu „Fahrräder“ gehört. Wie zeigt der Shop über der Artikelseite den Pfad Fahrräder > Lastenräder > E-Lastenräder > Long John an, wenn jede Kategorie nur ihre direkte Oberkategorie kennt? Wie berechnet ein Dateimanager die Größe eines Ordners, der Unterordner enthält, die wieder Unterordner enthalten? Für solche Aufgaben gibt es eine verblüffend kurze Lösung: Die Funktion erledigt einen kleinen Teil der Arbeit selbst und überlässt den Rest – sich selbst.

Dieses Prinzip heißt Rekursion (von lateinisch recurrere, „zurücklaufen“). Es gehört zu den Grundtechniken der Programmierung und taucht in Aufgaben der Anwendungsentwicklung mit Schreibtischtest, Fehlersuche, Vor- und Nachteilen und der Umwandlung in eine Schleife auf.

Die Schreibweise in diesem Artikel

Der Pseudocode folgt dem Artikel Prozedurale Algorithmen mit Arrays; vorausgewählt ist das deutsche Pseudo-Pascal: := ist die Zuweisung, = und <> vergleichen, div ist die ganzzahlige Division und mod der Rest, Arrays beginnen beim Index 0. Neu hinzu kommen:

Die Codebeispiele kannst Du in vier Notationen anzeigen. Die Notationen sind im Artikel Algorithmen mit Pseudocode dokumentieren beschrieben.

Was ist Rekursion – und was ist Iteration?

Eine Funktion (Methode, Prozedur) ist rekursiv, wenn sie sich selbst aufruft – direkt in ihrem eigenen Rumpf (direkte Rekursion) oder auf einem Umweg über eine andere Funktion, die wiederum die erste aufruft (indirekte oder wechselseitige Rekursion).

Iteration (von lateinisch iterare, „wiederholen“) löst dieselbe Art von Problemen mit einer Schleife: Ein Block wird so lange wiederholt, bis eine Bedingung erfüllt ist. Der Zwischenstand steht dabei in Variablen, die bei jedem Durchlauf überschrieben werden.

Viele Größen sind schon in der Mathematik rekursiv definiert. Die Fakultät zum Beispiel:

n! = \begin{cases} 1 & \text{für } n \leq 1 \\ n \cdot (n-1)! & \text{für } n > 1 \end{cases}

Die Definition stützt sich auf sich selbst – aber immer mit einer kleineren Zahl, und für kleine Zahlen steht das Ergebnis direkt fest. Genau so ist auch eine rekursive Funktion gebaut:

JANA Pseudo-Pascal Pseudo-Pascal (deutsch) Pseudo-Python all none

int fakultaet(int n) {
    if (n <= 1) {
        return 1                         // Abbruchbedingung (Basisfall)
    }
    return n * fakultaet(n - 1)          // Rekursionsschritt
}

FUNCTION fakultaet(n: integer) : integer
    if (n <= 1) then
        RETURN 1                         // Abbruchbedingung (Basisfall)
    end if
    RETURN n * fakultaet(n - 1)          // Rekursionsschritt
END fakultaet

Funktion fakultaet(n: integer): integer
    wenn n <= 1 dann
        Rückgabe 1                       // Abbruchbedingung (Basisfall)
    Ende wenn
    Rückgabe n * fakultaet(n - 1)        // Rekursionsschritt
Ende fakultaet

def fakultaet(n):
    if n <= 1:
        return 1                         # Abbruchbedingung (Basisfall)
    # Ende if
    return n * fakultaet(n - 1)          # Rekursionsschritt
# Ende fakultaet

In Java sieht das fast genauso aus:

static long fakultaet(int n) {
    if (n <= 1) {
        return 1;                        // Abbruchbedingung
    }
    return n * fakultaet(n - 1);         // Rekursionsschritt
}

Zum Vergleich die iterative Fassung mit einer Zählschleife:

JANA Pseudo-Pascal Pseudo-Pascal (deutsch) Pseudo-Python all none

int fakultaetIterativ(int n) {
    int ergebnis = 1
    for (int i = 2 … n) {
        ergebnis = ergebnis * i
    }
    return ergebnis
}

FUNCTION fakultaetIterativ(n: integer) : integer
    ergebnis: integer := 1
    for i := 2 to n do
        ergebnis := ergebnis * i
    end for
    RETURN ergebnis
END fakultaetIterativ

Funktion fakultaetIterativ(n: integer): integer
    ergebnis: integer := 1
    zähle i von 2 bis n
        ergebnis := ergebnis * i
    Ende zähle
    Rückgabe ergebnis
Ende fakultaetIterativ

def fakultaetIterativ(n):
    ergebnis = 1
    for i in range(2, n + 1):
        ergebnis = ergebnis * i
    # Ende for
    return ergebnis
# Ende fakultaetIterativ

Die zwei Zutaten: Abbruchbedingung und Rekursionsschritt

Jede funktionierende Rekursion besteht aus zwei Teilen:

• Die Abbruchbedingung (auch Basisfall, Rekursionsanker, englisch base case) behandelt den kleinsten Fall direkt, ohne weiteren Aufruf. Bei der Fakultät: n <= 1 liefert 1.

• Der Rekursionsschritt (recursive case) zerlegt das Problem, ruft die Funktion mit einem kleineren Teilproblem auf und baut aus dessen Ergebnis das eigene Ergebnis zusammen: n * fakultaet(n - 1).

Wenn Du einen rekursiven Algorithmus schreibst oder prüfst, helfen drei Fragen:

1. Gibt es eine Abbruchbedingung, und wird sie vor dem rekursiven Aufruf geprüft?

2. Wird das Problem bei jedem Aufruf kleiner (kleinere Zahl, kürzerer Bereich, tieferer Knoten)?

3. Wird die Abbruchbedingung für jede zulässige Eingabe tatsächlich erreicht – auch für 0, negative Werte, leere Arrays oder fehlerhafte Daten?

Ist eine der drei Antworten „nein“, ruft sich die Funktion endlos selbst auf. Was dann passiert, zeigt der nächste Abschnitt.

Was beim Aufruf passiert: der Aufrufstapel

Jeder Funktionsaufruf bekommt im Arbeitsspeicher einen eigenen Bereich, den Stapelrahmen (stack frame). Darin liegen die Parameter, die lokalen Variablen und die Rücksprungadresse, also die Stelle, an der nach dem Ende des Aufrufs weitergearbeitet wird. Die Rahmen werden auf dem Aufrufstapel (call stack) übereinandergelegt: Der jüngste Aufruf liegt oben und wird als erster beendet (Last In, First Out).

Bei Rekursion bedeutet das: Jede Aufrufebene hat ihre eigenen Werte von n. Die Ebenen beeinflussen sich nicht gegenseitig, solange sie nicht auf gemeinsame (globale) Variablen zugreifen. Für fakultaet(4) wächst der Stapel auf vier Rahmen an und baut sich dann wieder ab:

Der Stapel ist begrenzt. Bei Java hat jeder Thread einen eigenen Stapelspeicher fester Größe (bei HotSpot auf 64-Bit-Systemen standardmäßig rund 1 MiB, einstellbar mit der Option -Xss). Endet eine Rekursion nie oder ist sie sehr tief, ist der Stapel irgendwann voll: Es kommt zum Stapelüberlauf (stack overflow), in Java zum StackOverflowError, und das Programm bricht ab.

static long fakultaetFalsch(int n) {
    return n * fakultaetFalsch(n - 1);   // keine Abbruchbedingung
}
// fakultaetFalsch(4) → java.lang.StackOverflowError

Die Aufruftiefe (Rekursionstiefe) ist die höchste Zahl gleichzeitig offener Aufrufe. Sie bestimmt den Speicherbedarf einer Rekursion: Tiefe mal Größe eines Stapelrahmens. Eine Iteration braucht dagegen unabhängig von der Zahl der Durchläufe nur die Variablen eines einzigen Aufrufs.

Abstieg und Aufstieg: Wann passiert was?

Eine rekursive Funktion durchläuft zwei Phasen. Beim Abstieg (winding) ruft jede Ebene die nächste auf, bis die Abbruchbedingung erreicht ist. Beim Aufstieg (unwinding) werden die Aufrufe von innen nach außen beendet, und jede Ebene führt aus, was hinter ihrem rekursiven Aufruf steht.

Für die Reihenfolge von Ausgaben ist deshalb entscheidend, wo sie stehen:

JANA Pseudo-Pascal Pseudo-Pascal (deutsch) Pseudo-Python all none

zaehle(int n) {
    if (n > 0) {
        write(n + " ")       // (A) vor dem Aufruf: beim Abstieg
        zaehle(n - 1)
        write(n + " ")       // (B) nach dem Aufruf: beim Aufstieg
    }
}

PROCEDURE zaehle(n: integer)
    if (n > 0) then
        write(n & " ")       // (A) vor dem Aufruf: beim Abstieg
        zaehle(n - 1)
        write(n & " ")       // (B) nach dem Aufruf: beim Aufstieg
    end if
END zaehle

Prozedur zaehle(n: integer)
    wenn n > 0 dann
        Ausgabe n & " "      // (A) vor dem Aufruf: beim Abstieg
        zaehle(n - 1)
        Ausgabe n & " "      // (B) nach dem Aufruf: beim Aufstieg
    Ende wenn
Ende zaehle

def zaehle(n):
    if n > 0:
        print(str(n) + " ", end="")   # (A) vor dem Aufruf: beim Abstieg
        zaehle(n - 1)
        print(str(n) + " ", end="")   # (B) nach dem Aufruf: beim Aufstieg
    # Ende if
# Ende zaehle

Der Aufruf zaehle(3) gibt 3 2 1 1 2 3 aus: Die Ausgaben (A) erscheinen beim Abstieg in der Reihenfolge der Aufrufe (äußerste Ebene zuerst), die Ausgaben (B) beim Aufstieg in umgekehrter Reihenfolge (innerste Ebene zuerst).

Dieses Verhalten kannst Du gezielt nutzen. Beim Divisionsrestverfahren zur Umrechnung einer Zahl in ein anderes Stellenwertsystem (dual, oktal, hexadezimal) entsteht die niederwertigste Stelle zuerst, ausgegeben werden soll aber die höchstwertige zuerst. Steht die Ausgabe nach dem rekursiven Aufruf, erledigt der Aufstieg das Umdrehen:

JANA Pseudo-Pascal Pseudo-Pascal (deutsch) Pseudo-Python all none

schreibeInBasis(int zahl, int basis) {
    if (zahl >= basis) {
        schreibeInBasis(zahl / basis, basis)     // erst die höherwertigen Stellen ...
    }
    write(ziffer(zahl % basis))                  // ... dann die eigene Stelle
}

PROCEDURE schreibeInBasis(zahl: integer, basis: integer)
    if (zahl >= basis) then
        schreibeInBasis(zahl div basis, basis)   // erst die höherwertigen Stellen ...
    end if
    write(ziffer(zahl mod basis))                // ... dann die eigene Stelle
END schreibeInBasis

Prozedur schreibeInBasis(zahl: integer, basis: integer)
    wenn zahl >= basis dann
        schreibeInBasis(zahl div basis, basis)   // erst die höherwertigen Stellen ...
    Ende wenn
    Ausgabe ziffer(zahl mod basis)               // ... dann die eigene Stelle
Ende schreibeInBasis

def schreibeInBasis(zahl, basis):
    if zahl >= basis:
        schreibeInBasis(zahl // basis, basis)    # erst die höherwertigen Stellen ...
    # Ende if
    print(ziffer(zahl % basis), end="")          # ... dann die eigene Stelle
# Ende schreibeInBasis

ziffer(w) liefert das Ziffernzeichen für den Wert w (0 … 9, A … F). Die Bedingung zahl >= basis sorgt dafür, dass auch die Zahl 0 korrekt als 0 ausgegeben wird. Stünde die Ausgabe vor dem Aufruf, kämen die Stellen in umgekehrter Reihenfolge heraus – ein typischer Fehler.

Schreibtischtest bei rekursiven Algorithmen

Beim Schreibtischtest (siehe Unit-Tests und Schreibtischtest) notierst Du jeden Aufruf als eigene Zeile, so wie er auf dem Stapel liegt. In die Spalten kommen die Parameter, das Ergebnis der Abbruchprüfung, der nächste Aufruf und – getrennt – was beim Abstieg und was beim Aufstieg passiert. Für schreibeInBasis(300, 16):

Gesamtausgabe: 12C. Gegenprobe: 1 \cdot 16^2 + 2 \cdot 16 + 12 = 300.

Bei Funktionen mit Rückgabewert setzt Du die Rückgabewerte von unten nach oben ein, so wie in der Tabelle zur Fakultät oben. Vergleiche am Ende das Ergebnis mit dem erwarteten Ergebnis. Weichen beide voneinander ab, suchst Du die Ursache in der Reihenfolge, der Abbruchbedingung oder in der Verkleinerung des Problems.

Typische Fehler in rekursiven Algorithmen

• Abbruchbedingung fehlt oder wird nie erreicht: Das Problem wird nicht kleiner (f(n) statt f(n - 1)), der Bereich schrumpft nicht (mitte statt mitte + 1) oder ein Sonderfall springt über die Bedingung hinweg (wenn n = 0 bei negativem n). Folge: Endlosrekursion und Stapelüberlauf.

• Datenfehler erzeugen Zyklen: Zeigt eine Kategorie durch einen Importfehler auf sich selbst als Oberkategorie, läuft der Pfadaufbau endlos. Abhilfe: Daten prüfen (z. B. Fremdschlüssel und CHECK-Bedingung in der Datenbank), zusätzlich eine maximale Tiefe als Parameter mitgeben.

• Anweisung an der falschen Stelle: Ausgabe vor statt nach dem rekursiven Aufruf (oder umgekehrt) – die Teilergebnisse erscheinen in umgekehrter Reihenfolge.

• Rückgabewert des rekursiven Aufrufs geht verloren: f(n - 1) wird aufgerufen, aber das Ergebnis nicht zurückgegeben oder weiterverwendet. In Java meldet der Compiler dann oft missing return statement; im Pseudocode bleibt der Fehler unbemerkt.

• Abbruchprüfung zu spät: Erst wird auf werte[i] zugegriffen, dann geprüft, ob i noch im Array liegt – bei einem leeren Array oder am Rand ein Laufzeitfehler.

• Gemeinsame Variablen: Eine globale Zählvariable, die alle Ebenen verändern, führt zu schwer nachvollziehbaren Ergebnissen. Besser: Werte als Parameter hinein- und als Rückgabewert herausreichen.

Aus Rekursion wird Iteration

Jede Rekursion lässt sich in eine Iteration umwandeln – im einfachsten Fall mit einer Schleife, im allgemeinen Fall mit einem selbst verwalteten Stapel, der den Aufrufstapel nachbildet.

Fall 1: Das Ergebnis wird nur weitergereicht. Bei der Fakultät oder beim Zählen läuft die Rekursion „in einer Linie“. Die Abbruchbedingung wird zur Schleifenbedingung, der Parameter zur Laufvariablen und das Zwischenergebnis wandert in eine Variable – siehe fakultaetIterativ oben.

Fall 2: Die Reihenfolge muss umgekehrt werden. Bei schreibeInBasis hat der Aufrufstapel die Stellen zwischengespeichert, damit sie beim Aufstieg rückwärts ausgegeben werden. Die Iteration braucht dafür eine Hilfsdatenstruktur: eine Liste, die Du rückwärts ausliest, oder einen Stapel, von dem Du die zuletzt abgelegte Stelle zuerst entnimmst.

JANA Pseudo-Pascal Pseudo-Pascal (deutsch) Pseudo-Python all none

schreibeInBasisIterativ(int zahl, int basis) {
    Liste stellen = new Liste()
    repeat {                                     // fußgesteuert: auch 0 ergibt eine Stelle
        stellen.anhaengen(ziffer(zahl % basis))
        zahl = zahl / basis
    } until (zahl == 0)
    for (int i = stellen.anzahl()-1, stellen.anzahl()-2, …, 0) {
        write(stellen.element(i))
    }
}

PROCEDURE schreibeInBasisIterativ(zahl: integer, basis: integer)
    stellen: Liste := new Liste()
    repeat                                       // fußgesteuert: auch 0 ergibt eine Stelle
        stellen.anhaengen(ziffer(zahl mod basis))
        zahl := zahl div basis
    until (zahl = 0)
    for i := stellen.anzahl() - 1 downto 0 do
        write(stellen.element(i))
    end for
END schreibeInBasisIterativ

Prozedur schreibeInBasisIterativ(zahl: integer, basis: integer)
    stellen: Liste := new Liste()
    wiederhole                                   // fußgesteuert: auch 0 ergibt eine Stelle
        stellen.anhaengen(ziffer(zahl mod basis))
        zahl := zahl div basis
    solange zahl <> 0
    zähle i von stellen.anzahl() - 1 bis 0 Schrittweite -1
        Ausgabe stellen.element(i)
    Ende zähle
Ende schreibeInBasisIterativ

def schreibeInBasisIterativ(zahl, basis):
    stellen = Liste()
    do:                                          # fußgesteuert: auch 0 ergibt eine Stelle
        stellen.anhaengen(ziffer(zahl % basis))
        zahl = zahl // basis
    while (zahl != 0)
    for i in range(stellen.anzahl() - 1, -1, -1):
        print(stellen.element(i), end="")
    # Ende for
# Ende schreibeInBasisIterativ

Achte dabei besonders auf drei Stellen:

• Indexgrenzen: Eine Liste mit anzahl() Elementen hat die Positionen 0 bis anzahl() - 1. Wer bei anzahl() beginnt, greift ins Leere.

• Bedeutung der Positionen: Lies genau, wie die vorgegebene Klasse ihre Positionen zählt (vom Anfang oder vom Ende her) und an welcher Stelle sie einfügt. Davon hängt ab, ob Du auf- oder abwärts zählen musst.

• Sonderfälle: Eine kopfgesteuerte Schleife solange zahl > 0 gibt für die Zahl 0 gar nichts aus. Eine fußgesteuerte Schleife oder eine eigene Abfrage löst das.

Statt einer Hilfsliste kannst Du die Ausgabe auch als Zeichenkette von rechts nach links aufbauen: text := ziffer(zahl mod basis) & text. Das ist kürzer, verschiebt das Umdrehen aber in die Zeichenkettenverkettung.

Fall 3: Mehrere rekursive Aufrufe. Bei Bäumen (nächster Abschnitt) merkt sich der Aufrufstapel, welche Zweige noch offen sind. Iterativ legst Du die noch zu besuchenden Knoten selbst auf einen Stapel (Tiefensuche) oder in eine Warteschlange (Breitensuche). Das funktioniert, ist aber meist länger und schwerer zu lesen als die rekursive Fassung.

Aus Iteration wird Rekursion

Umgekehrt kannst Du jede Schleife als Rekursion schreiben. Das Rezept:

1. Die Laufvariable der Schleife wird ein Parameter der Funktion.

2. Die negierte Schleifenbedingung wird zur Abbruchbedingung.

3. Der Schleifenrumpf wird ausgeführt, danach folgt der rekursive Aufruf mit dem nächsten Wert der Laufvariablen.

4. Ein Zwischenergebnis (Summe, Zähler) wird entweder über die Rückgabe zusammengesetzt oder als zusätzlicher Parameter mitgegeben.

5. Der Erstaufruf setzt den Startwert der Laufvariablen.

Beispiel: die Summe aller Werte eines Arrays.

JANA Pseudo-Pascal Pseudo-Pascal (deutsch) Pseudo-Python all none

// iterativ
int summe = 0
for (int i = 0 … length(werte)-1) {
    summe = summe + werte[i]
}

// rekursiv
int summeAb(int werte[], int i) {
    if (i >= length(werte)) {                    // negierte Schleifenbedingung
        return 0
    }
    return werte[i] + summeAb(werte, i + 1)      // Rumpf + nächster Wert
}

// Erstaufruf
int gesamt = summeAb(werte, 0)

// iterativ
summe: integer := 0
for i := 0 to length(werte) - 1 do
    summe := summe + werte[i]
end for

// rekursiv
FUNCTION summeAb(werte: array of integer, i: integer) : integer
    if (i >= length(werte)) then                 // negierte Schleifenbedingung
        RETURN 0
    end if
    RETURN werte[i] + summeAb(werte, i + 1)      // Rumpf + nächster Wert
END summeAb

// Erstaufruf
gesamt: integer := summeAb(werte, 0)

// iterativ
summe: integer := 0
zähle i von 0 bis laenge(werte) - 1
    summe := summe + werte[i]
Ende zähle

// rekursiv
Funktion summeAb(werte: integer[], i: integer): integer
    wenn i >= laenge(werte) dann                 // negierte Schleifenbedingung
        Rückgabe 0
    Ende wenn
    Rückgabe werte[i] + summeAb(werte, i + 1)    // Rumpf + nächster Wert
Ende summeAb

// Erstaufruf
gesamt: integer := summeAb(werte, 0)

# iterativ
summe = 0
for i in range(len(werte)):
    summe = summe + werte[i]
# Ende for

# rekursiv
def summeAb(werte, i):
    if i >= len(werte):                          # negierte Schleifenbedingung
        return 0
    # Ende if
    return werte[i] + summeAb(werte, i + 1)      # Rumpf + nächster Wert
# Ende summeAb

# Erstaufruf
gesamt = summeAb(werte, 0)

Für so eine einfache Schleife ist die Rekursion kein Gewinn – im Gegenteil: Bei einem Array mit 100.000 Werten liegen 100.001 Rahmen auf dem Stapel. Das Rezept lohnt sich, wenn eine Aufgabe ausdrücklich Rekursion verlangt oder wenn das Problem selbst rekursiv ist.

Bäume: Wo Rekursion zu Hause ist

Viele Daten sind selbstähnlich aufgebaut: Ein Ordner enthält Dateien und Ordner, eine Kategorie enthält Artikel und Unterkategorien, ein Bauteil besteht aus Bauteilen. In Datenbanken heißen solche Strukturen rekursive Beziehungen – eine Tabelle verweist über einen Fremdschlüssel auf sich selbst, z. B. kategorie.ober_kategorie_id (siehe Relationenmodell).

Für solche Bäume ist Rekursion die natürliche Lösung: Ein Aufruf behandelt einen Knoten und ruft sich für jedes Kind auf. Die Abbruchbedingung steckt oft unsichtbar in der Schleife – ein Ordner ohne Unterordner löst keinen weiteren Aufruf aus.

JANA Pseudo-Pascal Pseudo-Pascal (deutsch) Pseudo-Python all none

int ordnergroesse(Ordner ordner) {
    int summe = 0
    Datei dateien[] = ordner.dateien()
    for (int i = 0 … length(dateien)-1) {
        summe = summe + dateien[i].groesse()
    }
    Ordner unter[] = ordner.unterordner()
    for (int i = 0 … length(unter)-1) {
        summe = summe + ordnergroesse(unter[i])    // ein Aufruf je Unterordner
    }
    return summe
}

FUNCTION ordnergroesse(ordner: Ordner) : integer
    summe: integer := 0
    dateien: array of Datei := ordner.dateien()
    for i := 0 to length(dateien) - 1 do
        summe := summe + dateien[i].groesse()
    end for
    unter: array of Ordner := ordner.unterordner()
    for i := 0 to length(unter) - 1 do
        summe := summe + ordnergroesse(unter[i])   // ein Aufruf je Unterordner
    end for
    RETURN summe
END ordnergroesse

Funktion ordnergroesse(ordner: Ordner): integer
    summe: integer := 0
    dateien: Datei[] := ordner.dateien()
    zähle i von 0 bis laenge(dateien) - 1
        summe := summe + dateien[i].groesse()
    Ende zähle
    unter: Ordner[] := ordner.unterordner()
    zähle i von 0 bis laenge(unter) - 1
        summe := summe + ordnergroesse(unter[i])   // ein Aufruf je Unterordner
    Ende zähle
    Rückgabe summe
Ende ordnergroesse

def ordnergroesse(ordner):
    summe = 0
    dateien = ordner.dateien()
    for i in range(len(dateien)):
        summe = summe + dateien[i].groesse()
    # Ende for
    unter = ordner.unterordner()
    for i in range(len(unter)):
        summe = summe + ordnergroesse(unter[i])    # ein Aufruf je Unterordner
    # Ende for
    return summe
# Ende ordnergroesse

Als Struktogramm sieht dieselbe Funktion so aus. Der rekursive Aufruf ist ein gewöhnlicher Strukturblock; im Programmablaufplan nach DIN 66001 würdest Du ihn als Unterprogramm (Rechteck mit doppelten senkrechten Seitenlinien) zeichnen.

Die Funktion wird für jeden Ordner des Baums genau einmal aufgerufen. Die Aufruftiefe entspricht der Verschachtelungstiefe der Ordner – bei Dateisystemen und Kategoriebäumen sind das selten mehr als einige Dutzend Ebenen, der Stapel ist hier also kein Problem.

Teile und herrsche

Eine zweite Familie rekursiver Algorithmen zerlegt ein Problem in Hälften statt in „eins und den Rest“. Dieses Prinzip heißt Teile und herrsche (divide and conquer): teilen, Teilprobleme rekursiv lösen, Ergebnisse zusammensetzen. Bekannte Beispiele sind die binäre Suche in einem sortierten Array, Mergesort und Quicksort (siehe Sortieralgorithmen).

Ein kleines Beispiel ist die schnelle Potenz: Statt x^{10} mit zehn Multiplikationen zu berechnen, nutzt Du x^{10} = (x^5)^2 und x^5 = x \cdot (x^2)^2.

JANA Pseudo-Pascal Pseudo-Pascal (deutsch) Pseudo-Python all none

float potenz(float x, int n) {                // n >= 0
    if (n == 0) {
        return 1
    }
    float h = potenz(x, n / 2)                // ein Aufruf für die halbe Hochzahl
    if (n % 2 == 0) {
        return h * h
    } else {
        return h * h * x
    }
}

FUNCTION potenz(x: real, n: integer) : real   // n >= 0
    if (n = 0) then
        RETURN 1
    end if
    h: real := potenz(x, n div 2)             // ein Aufruf für die halbe Hochzahl
    if (n mod 2 = 0) then
        RETURN h * h
    else
        RETURN h * h * x
    end if
END potenz

Funktion potenz(x: double, n: integer): double   // n >= 0
    wenn n = 0 dann
        Rückgabe 1
    Ende wenn
    h: double := potenz(x, n div 2)           // ein Aufruf für die halbe Hochzahl
    wenn n mod 2 = 0 dann
        Rückgabe h * h
    sonst
        Rückgabe h * h * x
    Ende wenn
Ende potenz

def potenz(x, n):                             # n >= 0
    if n == 0:
        return 1
    # Ende if
    h = potenz(x, n // 2)                     # ein Aufruf für die halbe Hochzahl
    if n % 2 == 0:
        return h * h
    else:
        return h * h * x
    # Ende if
# Ende potenz

Da sich der Parameter bei jedem Aufruf halbiert, wächst die Aufruftiefe nur mit dem Logarithmus: Für n sind es \lfloor \log_2 n \rfloor + 2 Aufrufe (für n = 10: 10, 5, 2, 1, 0 – also 5 Aufrufe), für n = 1.000.000 nur 21. Bei der binären Suche gilt dasselbe: Mit jedem Vergleich halbiert sich der Suchbereich, für 1.000 sortierte Werte genügen höchstens 10 Vergleiche.

Mehrfache Rekursion und ihre Kosten

Ruft sich eine Funktion zweimal mit fast gleich großen Teilproblemen auf, kann der Aufwand explodieren. Das klassische Beispiel sind die Fibonacci-Zahlen (F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}):

JANA Pseudo-Pascal Pseudo-Pascal (deutsch) Pseudo-Python all none

int fib(int n) {
    if (n < 2) {
        return n
    }
    return fib(n - 1) + fib(n - 2)
}

FUNCTION fib(n: integer) : integer
    if (n < 2) then
        RETURN n
    end if
    RETURN fib(n - 1) + fib(n - 2)
END fib

Funktion fib(n: integer): integer
    wenn n < 2 dann
        Rückgabe n
    Ende wenn
    Rückgabe fib(n - 1) + fib(n - 2)
Ende fib

def fib(n):
    if n < 2:
        return n
    # Ende if
    return fib(n - 1) + fib(n - 2)
# Ende fib

Der Aufruf fib(5) löst insgesamt 15 Aufrufe aus, weil fib(3) zweimal, fib(2) dreimal und fib(1) fünfmal berechnet wird. Für fib(30) sind es schon 2.692.537 Aufrufe. Die Aufruftiefe bleibt dabei klein (höchstens n), aber die Rechenzeit wächst exponentiell.

Abhilfe schafft Memoisation: Die Funktion merkt sich bereits berechnete Ergebnisse in einem Array oder einer Map und gibt sie beim nächsten Mal direkt zurück. Dann wird jedes fib(k) nur einmal berechnet. Noch einfacher ist hier die Iteration mit zwei Variablen für die letzten beiden Werte.

Endrekursion

Eine Funktion ist endrekursiv (tail recursive), wenn der rekursive Aufruf die letzte Aktion ist und sein Ergebnis unverändert zurückgegeben wird. fakultaet ist nicht endrekursiv, denn nach dem Aufruf wird noch mit n multipliziert. Mit einem zusätzlichen Parameter, dem Akkumulator, lässt sie sich endrekursiv schreiben:

JANA Pseudo-Pascal Pseudo-Pascal (deutsch) Pseudo-Python all none

int fakultaetEnd(int n, int akku) {
    if (n <= 1) {
        return akku
    }
    return fakultaetEnd(n - 1, akku * n)     // nichts mehr zu tun nach dem Aufruf
}

// Erstaufruf: fakultaetEnd(4, 1)

FUNCTION fakultaetEnd(n: integer, akku: integer) : integer
    if (n <= 1) then
        RETURN akku
    end if
    RETURN fakultaetEnd(n - 1, akku * n)     // nichts mehr zu tun nach dem Aufruf
END fakultaetEnd

// Erstaufruf: fakultaetEnd(4, 1)

Funktion fakultaetEnd(n: integer, akku: integer): integer
    wenn n <= 1 dann
        Rückgabe akku
    Ende wenn
    Rückgabe fakultaetEnd(n - 1, akku * n)   // nichts mehr zu tun nach dem Aufruf
Ende fakultaetEnd

// Erstaufruf: fakultaetEnd(4, 1)

def fakultaetEnd(n, akku):
    if n <= 1:
        return akku
    # Ende if
    return fakultaetEnd(n - 1, akku * n)     # nichts mehr zu tun nach dem Aufruf
# Ende fakultaetEnd

# Erstaufruf: fakultaetEnd(4, 1)

Weil nach dem Aufruf nichts mehr zu tun ist, braucht der alte Stapelrahmen nicht aufgehoben zu werden. Manche Compiler ersetzen endrekursive Aufrufe deshalb durch einen Sprung an den Funktionsanfang (tail call optimization) – die Rekursion läuft dann mit konstantem Speicher wie eine Schleife. Das tun etwa viele Compiler funktionaler Sprachen; in Kotlin erzwingt das Schlüsselwort tailrec die Umwandlung. Java und die JVM optimieren endrekursive Aufrufe nicht, auch Python nicht. Dort bleibt der Stapelüberlauf bei großer Tiefe ein Risiko, und eine Schleife ist die sichere Wahl.

Rekursion oder Iteration?

Eine Faustregel für die Praxis: Ist die Datenstruktur oder das Verfahren rekursiv und die Tiefe begrenzt (Baum, Teile und herrsche), spricht viel für Rekursion. Ist es eine einfache Wiederholung über viele Elemente oder kann die Tiefe mit der Datenmenge unbegrenzt wachsen, ist die Iteration robuster.

Verlangt eine Aufgabe, je einen Vor- und Nachteil zu beschreiben, reicht ein vollständiger Satz je Punkt mit Begründung, z. B.: „Vorteil: Die rekursive Lösung ist kürzer und leichter zu lesen, weil sie die rekursive Definition direkt abbildet. Nachteil: Sie benötigt mehr Arbeitsspeicher, weil für jeden Aufruf ein eigener Stapelrahmen angelegt wird.“

Rekursion testen

Für die Anweisungsüberdeckung (siehe Codecoverage) muss jede Anweisung mindestens einmal ausgeführt werden. Bei einer rekursiven Funktion genügt dafür oft ein einziger Testfall: Ein Aufruf, der mindestens einen Rekursionsschritt auslöst, erreicht im Laufe der Rekursion auch den Basisfall. Bei zaehle(1) wird erst der Rumpf mit n = 1 ausgeführt, im inneren Aufruf mit n = 0 dann die Abbruchbedingung. Oft ist damit sogar die Zweigüberdeckung erfüllt, weil die äußere Ebene den Ja-Zweig und die innerste Ebene den Nein-Zweig derselben Verzweigung nimmt.

Für einen guten Test reicht das trotzdem nicht. Prüfe zusätzlich:

• den Basisfall allein (z. B. 0, 1, leeres Array, Blatt ohne Kinder),

• Grenzwerte und unzulässige Eingaben (negative Zahl, null, Zyklus in den Daten),

• eine große Eingabe, die die erwartete maximale Aufruftiefe erreicht.

„Rekursiv“ außerhalb des Codes

Der Begriff begegnet Dir auch in anderen Zusammenhängen, mit verwandter Bedeutung: Shell-Befehle wie rm -r, cp -r oder chmod -R bearbeiten einen Ordner rekursiv, also mit allen Unterordnern – intern genau wie ordnergroesse. Bei der rekursiven DNS-Auflösung übernimmt dagegen ein Server die vollständige Auflösung für den Client, während er selbst die Root-, TLD- und zuständigen Nameserver nacheinander iterativ befragt. Mit Funktionsaufrufen hat das nur noch das Prinzip „jemand anderes erledigt den Rest“ gemeinsam.

Leitfragen

1. Was unterscheidet Rekursion von Iteration, und aus welchen zwei Teilen besteht jede funktionierende Rekursion? Antwort

Eine rekursive Funktion ruft sich selbst (direkt oder indirekt) mit einem kleineren Teilproblem auf, eine Iteration wiederholt dagegen einen Block in einer Schleife und hält den Zwischenstand in Variablen. Jede funktionierende Rekursion besteht aus der Abbruchbedingung (Basisfall), die den kleinsten Fall direkt löst, und dem Rekursionsschritt, der das Problem verkleinert und sich selbst aufruft, siehe Abschnitt „Was ist Rekursion – und was ist Iteration?“ und Abschnitt „Die zwei Zutaten: Abbruchbedingung und Rekursionsschritt“.

2. Wie führst Du einen Schreibtischtest für einen rekursiven Algorithmus durch, und woran erkennst Du, ob eine Anweisung beim Abstieg oder beim Aufstieg ausgeführt wird? Antwort

Du notierst jeden Aufruf als eigene Zeile (Aufrufebene) mit Parametern, Ergebnis der Abbruchprüfung, nächstem Aufruf und getrennt dem, was beim Abstieg und beim Aufstieg passiert; Rückgabewerte setzt Du von unten nach oben ein und vergleichst am Ende mit dem erwarteten Ergebnis. Anweisungen vor dem rekursiven Aufruf laufen beim Abstieg (äußerste Ebene zuerst), Anweisungen danach beim Aufstieg (innerste Ebene zuerst), siehe Abschnitt „Schreibtischtest bei rekursiven Algorithmen“ und Abschnitt „Abstieg und Aufstieg: Wann passiert was?“.

3. Was liegt auf dem Aufrufstapel, und wodurch kommt es zu einem Stapelüberlauf? Antwort

Auf dem Aufrufstapel liegt für jeden Aufruf ein Stapelrahmen mit Parametern, lokalen Variablen und Rücksprungadresse; der jüngste Aufruf liegt oben (LIFO). Weil der Stapel begrenzt ist, kommt es bei fehlender oder nie erreichter Abbruchbedingung oder bei sehr großer Aufruftiefe zum Stapelüberlauf (in Java StackOverflowError), siehe Abschnitt „Was beim Aufruf passiert: der Aufrufstapel“.

4. Welche Vor- und Nachteile hat eine rekursive gegenüber einer iterativen Lösung? Antwort

Rekursive Lösungen sind bei rekursiven Problemen (Bäume, Teile und herrsche, mathematische Definitionen) kürzer, näher an der Problembeschreibung und leicht als korrekt zu begründen. Dafür brauchen sie je Aufrufebene einen Stapelrahmen, also mehr Speicher, sind durch den Aufrufaufwand meist etwas langsamer, riskieren einen Stapelüberlauf und sind schwerer zu verfolgen, siehe Abschnitt „Rekursion oder Iteration?“.

5. Wie wandelst Du einen rekursiven Algorithmus in einen iterativen um, wenn die Reihenfolge umgekehrt werden muss – und worauf musst Du bei den Indexgrenzen achten? Antwort

Was bisher der Aufrufstapel beim Aufstieg umgedreht hat, speicherst Du in einer Hilfsdatenstruktur: Du legst die Teilergebnisse in einer Liste oder auf einem Stapel ab und liest sie anschließend rückwärts aus. Eine Liste mit anzahl() Elementen hat die Positionen 0 bis anzahl() - 1, die Rückwärtsschleife beginnt also bei anzahl() - 1; achte außerdem darauf, wie die vorgegebene Klasse Positionen zählt, und auf Sonderfälle wie die Zahl 0, siehe Abschnitt „Aus Rekursion wird Iteration“.

6. Wie wird aus einer Schleife eine rekursive Funktion, und wie lautet der Erstaufruf? Antwort

Die Laufvariable wird zum Parameter, die negierte Schleifenbedingung zur Abbruchbedingung, und nach dem Schleifenrumpf folgt der rekursive Aufruf mit dem nächsten Wert; ein Zwischenergebnis setzt Du über die Rückgabe zusammen oder reichst es als Parameter mit. Der Erstaufruf setzt den Startwert der Laufvariablen, z. B. gesamt := summeAb(werte, 0), siehe Abschnitt „Aus Iteration wird Rekursion“.

7. Warum eignet sich Rekursion besonders für Bäume und Teile-und-herrsche-Verfahren? Antwort

Bäume sind selbstähnlich aufgebaut: Ein Aufruf behandelt einen Knoten und ruft sich für jedes Kind auf, die Abbruchbedingung steckt im Knoten ohne Kinder, und die Aufruftiefe entspricht nur der Verschachtelungstiefe. Teile-und-herrsche-Verfahren halbieren das Problem bei jedem Aufruf, sodass die Aufruftiefe nur logarithmisch wächst (z. B. binäre Suche, schnelle Potenz), siehe Abschnitt „Bäume: Wo Rekursion zu Hause ist“ und Abschnitt „Teile und herrsche“.

8. Was ist Endrekursion, und warum hilft sie in Java nicht gegen den Stapelüberlauf? Antwort

Eine Funktion ist endrekursiv, wenn der rekursive Aufruf die letzte Aktion ist und sein Ergebnis unverändert zurückgegeben wird, oft mit einem Akkumulator als zusätzlichem Parameter. Manche Compiler ersetzen solche Aufrufe durch einen Sprung (tail call optimization), Java und die JVM tun das aber nicht, sodass jeder Aufruf weiterhin einen Stapelrahmen belegt und bei großer Tiefe ein Stapelüberlauf droht, siehe Abschnitt „Endrekursion“.

Links und weitere Informationen

• Übungsaufgaben zu Rekursion und Iteration

• Prozedurale Algorithmen mit Arrays

• Algorithmen mit Pseudocode dokumentieren

• Übersicht der Programmentwurfsmethoden (Pseudocode, Struktogramm, PAP, Aktivitätsdiagramm)

• Sortieralgorithmen und Vergleichsfunktionen

• Unit-Tests und Schreibtischtest

• Whitebox-Tests und Überdeckungsmaße

• Relationenmodell (rekursive Beziehungen)

• zum Nachschlagen: Java Language Specification, Kapitel 15.12 „Method Invocation Expressions“ und Java Virtual Machine Specification, Abschnitt 2.5.2 „Java Virtual Machine Stacks“

• zur Vertiefung: Kotlin-Dokumentation zu tailrec-Funktionen

Hinweis zur Nachnutzung als Open Educational Resource (OER)

Dieser Artikel und seine Texte, Bilder, Grafiken, Code und sonstiger Inhalt sind - sofern nicht anders angegeben - lizenziert unter CC BY 4.0. Nennung gemäß TULLU-Regel bitte wie folgt: “Rekursion und Iteration: Algorithmen, die sich selbst aufrufen” von oer-informatik.de (H. Stein), Lizenz: CC BY 4.0. Der Artikel wurde unter https://oer-informatik.de/rekursion veröffentlicht, die Quelltexte sind in weiterverarbeitbarer Form verfügbar im Repository unter https://gitlab.com/oer-informatik/algorithmik/algorithmen. Erstellt mit KI-Assistenz; von mir umfassend redaktionell überarbeitet, geprüft und freigegeben. Stand: 27.10.2026.

[Kommentare zum Artikel lesen, schreiben] / [Artikel teilen] / [gitlab-Issue zum Artikel schreiben]