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. sys.setrecursionlimit verschiebt nur die Grenze: Der nächste Import kann tiefer sein, und der echte Stack des Prozesses geht ohne Meldung zu Ende.

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:

def level_of(category, level):
    if category.parent is None:
        return level
    return level_of(category.parent, level + 1)

Hier ist der rekursive Aufruf das Letzte, was die Funktion 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:

last = chain(100_000)
while last.children:
    last = last.children[0]
try:
    print("Rekursion: Ebene " + str(level_of(last, 0)))
except RecursionError as e:
    print(f"Rekursion: RecursionError: {e}")
print("Schleife: Ebene " + str(level_of_loop(last)))
Ausgabe
Rekursion: RecursionError: maximum recursion depth exceeded
Schleife: Ebene 99999

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.
def level_of_loop(category):
    level = 0
    while category.parent is not None:
        category = category.parent
        level += 1
    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

count_products 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.

def count_products(root):
    total = 0
    stack = [root]
    while stack:
        category = stack.pop()
        total += category.products
        stack.extend(category.children)
    return total




print("Produkte: " + str(count_products(shop)))
Ausgabe
Produkte: 20

Eine Liste ist ein Stack: append und extend legen ans Ende, pop() nimmt vom Ende. Wie sie innen funktionieren, steht in der Lektion „Stack, Queue und verkettete Liste“.

Sieh es dir an

Dein eigener Stack, Schritt für Schritt

def count_products(root):
    total = 0
    stack = [root]
    while stack:
        category = stack.pop()
        total += category.products
        stack.extend(category.children)
    return total


print("Produkte: " + str(count_products(shop)))
Schritt für Schritt, in Worten
  1. Der Stack ist eine Liste 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:

def print_order(root):
    stack = [root]
    while stack:
        category = stack.pop()
        print(category.name)
        stack.extend(category.children)




print_order(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.

def print_menu(root):
    stack = [(root, 0)]
    while stack:
        category, level = stack.pop()
        print("  " * level + category.name)
        for child in reversed(category.children):
            stack.append((child, level + 1))




print_menu(shop)
Ausgabe
Shop
  Elektronik
    Smartphones
    Laptops
  Haushalt
    Küche
Der Stack hält Tupel (category, level). reversed() liest die Liste von hinten, 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:

deep = chain(100_000)
print(f"Tiefe 100000: {count_products(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:

def count_products(root):
    total = 0
    seen = set()
    stack = [root]
    while stack:
        category = stack.pop()
        if category in seen:
            print("Ich überspringe " + category.name + ": schon besucht")
            continue
        seen.add(category)
        total += category.products
        stack.extend(category.children)
    return total




kitchen.add(home)
print("Produkte: " + str(count_products(shop)))
Ausgabe
Ich überspringe Haushalt: schon besucht
Produkte: 20

Ein Objekt ohne __eq__ und __hash__ wird nach Identität verglichen: Das set hält die Kategorien selbst, nicht ihre Namen. Dieselbe Menge rettet auch die Rekursion: count_products 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. category = stack.pop()
  2. while stack:
  3. return total
  4. def count_products(root):
  5. stack = [root]
  6. total = 0
  7. total += category.products
  8. stack.extend(category.children)

Probier es aus

Ergänze

Wann hört die Schleife auf?

def count_products(root):
    total = 0
    stack = [root]
    while :
        category = stack.pop()
        total += category.products
        stack.extend(category.children)
    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
  • Python: Eine Liste ist ein schneller Stack (append und pop() am Ende sind O(1)). Für eine Queue nimm collections.deque: pop(0) bei einer Liste ist O(n).
  • Ein Generator mit yield from macht den rekursiven Durchlauf kurz, aber darunter gibt es trotzdem Frames: Die Tiefe stößt weiter an die Grenze von 1000.

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 ·