Zum Inhalt
wannacode

Von der Rekursion zur Schleife

Kurz gesagt: Eine Rekursion kann zu einer Schleife werden: Ein Endaufruf wird zu einer while-Schleife, und ein Baumdurchlauf wird zu einer Schleife mit eigenem Stack, der bei tiefen Daten nicht zu Ende geht.

Problem

Der Baum kommt von außen

In der Lektion „Der Aufrufstapel von innen“ scheiterte der Katalogdurchlauf an zwei Stellen: Die Kette aus dem Import war 100.000 Ebenen tief, und ein anderer Import schloss einen Kreis. Ein großer Stack ist keine Lösung. Ein größerer Stack verschiebt nur die Grenze: Der nächste Import kann tiefer sein.

Der Baum kommt von außen: von einem Lieferanten, von einer API, aus einer Datenbank. Du kannst nicht versprechen, wie tief er ist. Du brauchst einen Durchlauf, dessen Speicher nicht vom Aufrufstapel abhängt.

Die Idee

Endrekursion

Fang mit einer einfacheren Aufgabe an. Über einem Produkt zeigt der Shop die Ebene seiner Kategorie. Die Ebene wird über die Elternknoten nach oben gezählt, bis man die Wurzel erreicht:

static int levelOf(Category category, int level) {
    if (category.parent == null) {
        return level;
    }
    return levelOf(category.parent, level + 1);
}

Hier ist der rekursive Aufruf das Letzte, was die Methode tut: Sein Ergebnis wird direkt zurückgegeben, ohne + 1 und ohne Schleife danach. Ein solcher Aufruf ist ein Endaufruf (Tail Call), und die Rekursion ist Endrekursion. Danach muss sich der Frame nichts mehr merken. Eine Sprache, die das weiß, kann den Frame wiederverwenden, statt einen neuen anzulegen: Der Stack wächst nicht.

Aber:

  • Java tut es nicht. Die JVM behält jeden Frame.
  • Der C#-Compiler tut es nicht. Der JIT-Compiler tut es in optimiertem Code manchmal, aber es ist nicht versprochen: In unserem Test mit .NET 10 im Release lief der Stack trotzdem über.
  • Python tut es absichtlich nicht: Guido van Rossum ist dagegen, weil der Traceback Frames verlieren würde.
  • JavaScript muss es laut Standard tun (ES2015, im Strict Mode). In der Praxis tut es nur Safari. V8 (Chrome, Node) und Firefox nicht.

Deshalb scheitert Endrekursion auch an der Kette aus dem Import:

Category last = chain(100_000);
while (!last.children.isEmpty()) {
    last = last.children.get(0);
}
Category deepest = last;
Thread worker = new Thread(null, () -> {
    try {
        System.out.println("Rekursion: Ebene " + levelOf(deepest, 0));
    } catch (StackOverflowError e) {
        System.out.println("Rekursion: " + e);
    }
}, "catalog", 1024 * 1024);
worker.start();
worker.join();
System.out.println("Schleife: Ebene " + levelOfLoop(deepest));
Ausgabe
Rekursion: java.lang.StackOverflowError
Schleife: Ebene 99999
Die Rekursion läuft in einem Thread mit 1-MB-Stack, damit sie sich auf jedem Rechner gleich verhält.

Die Idee

Der Endaufruf wird zu while

Endrekursion wird mechanisch nach drei Regeln zu einer Schleife:

  • die Parameter werden zu Variablen: category und level;
  • der Aufruf wird zu einer Zuweisung: Statt dich mit den neuen Werten selbst aufzurufen, legst du sie in die Variablen und beginnst von vorn;
  • der Basisfall wird zur Endbedingung der Schleife: „kein Elternknoten“ beendet while.
static int levelOfLoop(Category category) {
    int level = 0;
    while (category.parent != null) {
        category = category.parent;
        level++;
    }
    return level;
}

Das ist die untere Zeile in der Ausgabe oben: Die Schleife kommt mit einem Frame bis zur Ebene 99.999. Rekursion und Schleife brauchen dieselbe Zahl von Schritten, einen pro Ebene. Der einzige Unterschied ist, wo der Speicher liegt.

Die Idee

Der Durchlauf ist kein Endaufruf

countProducts aus der vorigen Lektion ist keine Endrekursion. Nach jedem Aufruf gibt es Arbeit: total += und das nächste Kind in der Schleife. Deshalb werden die Frames gebraucht. Was haben sie wirklich gehalten? Die Kategorien, zu denen es noch nicht gekommen ist.

Das kann eine Schleife selbst halten, in einem eigenen Stack: einer Liste der noch ausstehenden Kategorien. Du nimmst die oberste, addierst ihre Produkte und legst ihre Kinder obenauf. Die Summe ist eine Variable, weil das Addieren nicht von der Reihenfolge abhängt.

static int countProducts(Category root) {
    int total = 0;
    Deque<Category> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Category category = stack.pop();
        total += category.products;
        for (Category child : category.children) {
            stack.push(child);
        }
    }
    return total;
}


System.out.println("Produkte: " + countProducts(shop));
Ausgabe
Produkte: 20

ArrayDeque ist Stack und Queue in einem: push legt oben drauf, pop nimmt von oben. Wie sie innen funktionieren, steht in der Lektion „Stack, Queue und verkettete Liste“.

Sieh es dir an

Dein eigener Stack, Schritt für Schritt

static int countProducts(Category root) {
    int total = 0;
    Deque<Category> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Category category = stack.pop();
        total += category.products;
        for (Category child : category.children) {
            stack.push(child);
        }
    }
    return total;
}


System.out.println("Produkte: " + countProducts(shop));
Schritt für Schritt, in Worten
  1. Der Stack ist ein ArrayDeque im Objektspeicher (Heap), nicht der Aufrufstapel. Zuerst kommt die Wurzel hinein.
  2. pop nimmt das oberste: Shop. Seine Kinder kommen obenauf: Elektronik, dann Haushalt.
  3. Als Nächstes kommt Haushalt, nicht Elektronik: Ein Stack gibt das zuletzt Hineingelegte zurück. total = 4, und Küche kommt hinein.
  4. Küche hat keine Kinder: Es kommt nichts hinein. total = 10.
  5. Erst jetzt Elektronik: total = 12. Smartphones und Laptops kommen hinein.
  6. Laptops (15), dann Smartphones (20).
  7. Der Stack ist leer: Die Schleife hört auf und liefert 20. Im Stack lagen nie mehr als 2 Kategorien. Die Reihenfolge ist aber Shop, Haushalt, Küche, Elektronik, Laptops, Smartphones: nicht die der Rekursion.

Dein eigener Stack ist ein gewöhnliches Objekt im Objektspeicher (dem Heap). Er wächst nach Bedarf und ist vom ganzen Speicher begrenzt, nicht von 1 MB. Und die Zahlen im Baum zeigen, dass die Reihenfolge anders ist.

Probier es aus

Sage die Reihenfolge voraus

Derselbe Durchlauf, aber er gibt den Namen jeder Kategorie aus, sobald er sie vom Stack nimmt:

static void printOrder(Category root) {
    Deque<Category> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Category category = stack.pop();
        System.out.println(category.name);
        for (Category child : category.children) {
            stack.push(child);
        }
    }
}


printOrder(shop);
Antwort

Die Idee

Die Reihenfolge der Rekursion: Kinder umgekehrt

Für die Summe spielt die Reihenfolge keine Rolle. Für das Menü schon: „Haushalt“ darf nicht vor „Elektronik“ stehen. Die Rekursion besucht zuerst den Elternknoten, dann die Kinder von links nach rechts (Pre-Order). Mit eigenem Stack kommt dieselbe Reihenfolge heraus, wenn du die Kinder umgekehrt hineinlegst: Das letzte Kind kommt zuerst hinein und zuletzt heraus.

Das Menü braucht auch Einrückung. Bei der Rekursion wäre die Ebene ein Parameter, also im Frame. Jetzt gibt es keinen Frame, also hält der Stack Paare: die Kategorie und ihre Ebene. Was der Frame hielt, hält jetzt dein Stack.

static void printMenu(Category root) {
    Deque<Entry> stack = new ArrayDeque<>();
    stack.push(new Entry(root, 0));
    while (!stack.isEmpty()) {
        Entry entry = stack.pop();
        Category category = entry.category();
        System.out.println("  ".repeat(entry.level()) + category.name);
        for (Category child : category.children.reversed()) {
            stack.push(new Entry(child, entry.level() + 1));
        }
    }
}


printMenu(shop);
Ausgabe
Shop
  Elektronik
    Smartphones
    Laptops
  Haushalt
    Küche
Entry ist ein Record mit den zwei Feldern: record Entry(Category category, int level) {}. children.reversed() (seit Java 21) ist eine Sicht, die die Liste von hinten liest, ohne sie zu kopieren.

Sieh es dir an

Der tiefe Baum kommt durch

Die Kette aus dem Import, 100.000 Ebenen, mit dem Durchlauf aus der Lektion:

Category deep = chain(100_000);
System.out.println("Tiefe 100000: " + countProducts(deep) + " Produkte");
Ausgabe
Tiefe 100000: 100000 Produkte

In allen vier Sprachen, ohne einen Thread mit großem Stack und ohne an irgendwelchen Grenzen zu drehen.

Ein Bench gibt es hier absichtlich nicht. Rekursion und Schleife machen dieselbe Zahl von Operationen: eine pro Kategorie, O(n). Die Kurven wären gleich. Der Unterschied liegt im Speicher: Die Rekursion hält bis zu Tiefe Frames auf dem kleinen Stack, die Schleife hält die wartenden Kategorien auf dem Heap. In einem breiten Baum kann dein eigener Stack groß werden (alle wartenden Geschwister), aber sein Platz ist der ganze Speicher.

Die Idee

Ein Kreis braucht ein Gedächtnis für das Gesehene

Dein eigener Stack rettet dich nicht vor einem Kreis. Liegt „Haushalt“ in „Küche“ und „Küche“ in „Haushalt“, wechseln sich die beiden ewig im Stack ab. Der Stack wächst nicht einmal, also läuft nichts über und nichts wird geworfen: Die Seite hängt einfach. Das ist schlimmer als der Fehler.

Die Abhilfe ist eine Menge der schon gesehenen Kategorien. Bevor du eine Kategorie durchläufst, prüfst du, ob sie schon in der Menge ist:

static int countProducts(Category root) {
    int total = 0;
    Set<Category> seen = new HashSet<>();
    Deque<Category> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Category category = stack.pop();
        if (!seen.add(category)) {
            System.out.println("Ich überspringe " + category.name + ": schon besucht");
            continue;
        }
        total += category.products;
        for (Category child : category.children) {
            stack.push(child);
        }
    }
    return total;
}


kitchen.add(home);
System.out.println("Produkte: " + countProducts(shop));
Ausgabe
Ich überspringe Haushalt: schon besucht
Produkte: 20

seen.add liefert false, wenn die Kategorie schon darin ist: eine Prüfung statt zwei. Category überschreibt equals und hashCode nicht, also vergleicht HashSet die Objekte selbst, nicht die Namen. Dieselbe Menge rettet auch die Rekursion: countProducts mit einem Parameter „gesehen“ stoppt den Kreis. Gegen die Tiefe hilft aber nur die Schleife.

Probier es aus

Bring die Zeilen in die richtige Reihenfolge

Bring den Durchlauf mit eigenem Stack in die richtige Reihenfolge:

  1. Deque<Category> stack = new ArrayDeque<>();
  2. }
  3. return total;
  4. for (Category child : category.children) {
  5. Category category = stack.pop();
  6. }
  7. stack.push(child);
  8. while (!stack.isEmpty()) {
  9. int total = 0;
  10. static int countProducts(Category root) {
  11. }
  12. stack.push(root);
  13. total += category.products;

Probier es aus

Ergänze

Wann hört die Schleife auf?

static int countProducts(Category root) {
    int total = 0;
    Deque<Category> stack = new ArrayDeque<>();
    stack.push(root);
    while () {
        Category category = stack.pop();
        total += category.products;
        for (Category child : category.children) {
            stack.push(child);
        }
    }
    return total;
}

Übung

Die tiefste Ebene

Löse die Aufgabe in deinem Editor.

Wie tief der Katalog ist. Der Import hängt seine Kette unter „Küche“. Lies, wie viele Ebenen die Kette hat, häng sie an und gib aus, wie viele Kategorien es insgesamt gibt und wie die tiefste Ebene ist (Shop liegt auf Ebene 0). Keine Rekursion: ein Stack aus Paaren von Kategorie und Ebene, wie im Menü.

Eingabe
100000
Ausgabe
Kategorien: 100006
Tiefste Ebene: 100002

Weitere Aufgaben

  • Der Brotkrumenpfad ohne Rekursion. Schreibe path aus der vorigen Lektion mit einer Schleife über die Elternknoten nach oben um. Die Liste wird von hinten gefüllt.
  • Das Menü mit den Produktzahlen. Gib das Menü aus, aber neben jeder Kategorie die Summe mit ihren Unterkategorien. Hinweis: Die Summe des Elternknotens ist erst nach seinen Kindern fertig, also kommt bei einer Schleife jede Kategorie zweimal in den Stack: einmal „offen“ und einmal „Summe“.

Genauer

Der Stack in jeder Sprache

Ein Stack wird in jeder Sprache anders geschrieben, und nicht jeder Stack ist eine gute Wahl.

Genauer, für Neugierige
  • Java: ArrayDeque ist der empfohlene Stack. Die alte Klasse Stack erweitert Vector: Sie synchronisiert jede Operation, ist also langsamer, und get(i) gibt auch Zugriff auf die Mitte des Stacks.
  • Rekursion in einem Thread mit großem Stack (new Thread(null, work, name, 64 * 1024 * 1024)) ist eine verbreitete Notlösung. Die Schleife ist die Korrektur.

Trampolin. Die Funktion ruft sich nicht selbst auf, sondern liefert „was als Nächstes aufzurufen ist“, und eine Schleife außerhalb ruft es auf. So läuft Endrekursion auch in Sprachen ohne Endaufrufe ohne wachsenden Stack. Es funktioniert, aber eine direkt geschriebene Schleife ist klarer.

Eine Queue statt eines Stacks. Benutzt du eine Queue (FIFO) statt eines Stacks, geht der Durchlauf Ebene für Ebene durch den Baum: Shop, dann Elektronik und Haushalt, dann Smartphones, Laptops und Küche. Das ist die Breitensuche (BFS). Sie findet den kürzesten Weg in einem Graphen, und du triffst sie im Modul „Graphen“.

Test

Teste dich

1. Welcher dieser Aufrufe ist ein Endaufruf?
2. Welche der vier Sprachen verwandelt Endrekursion in eine Schleife, sodass der Stack nicht wächst?
3. Warum kommt der Durchlauf mit eigenem Stack durch die Kette von 100.000 Ebenen, die Rekursion aber nicht?
4. Die Kinder einer Kategorie kommen in ihrer Reihenfolge in deinen eigenen Stack: Smartphones, dann Laptops. Was kommt zuerst heraus?
5. Was passiert, wenn der Durchlauf mit eigenem Stack auf einen Kreis trifft (Haushalt → Küche → Haushalt) und sich die gesehenen Kategorien nicht merkt?

Erstellt von Ivo Gergov im Rahmen der Kampagne von Evo Tech für zugängliche Programmierausbildung ·