Zum Inhalt
wannacode

Der Aufrufstapel von innen

Kurz gesagt: Der Aufrufstapel hält für jeden Aufruf, der noch nicht fertig ist, einen Frame; geht die Rekursion zu tief, hält Python das Programm mit RecursionError an.

Problem

Der Katalog, der die Seite lahmlegt

Das Menü eines Onlineshops ist ein Baum: Kategorien, darin Unterkategorien, in jeder ein paar Produkte. Neben dem Namen steht, wie viele Produkte es gibt, Unterkategorien eingeschlossen: „Elektronik (10)“. Eine rekursive Funktion zählt sie, wie in der Lektion „Rekursion“:

def count_products(category):
    total = category.products
    for child in category.children:
        total += count_products(child)
    return total




phones = Category("Smartphones", 5)
laptops = Category("Laptops", 3)
electronics = Category("Elektronik", 2).add(phones, laptops)
kitchen = Category("Küche", 6)
home = Category("Haushalt", 4).add(kitchen)
shop = Category("Shop", 0).add(electronics, home)
print("Produkte: " + str(count_products(shop)))
Ausgabe
Produkte: 20

Monatelang funktioniert es. Dann kommen zwei neue Importe von Lieferanten. Der erste setzt jede neue Kategorie in die vorige: Die Kette ist 100.000 Ebenen tief. Der zweite setzt aus Versehen „Haushalt“ in die eigene Unterkategorie „Küche“. In beiden Fällen scheitert die Seite mit RecursionError: maximum recursion depth exceeded.

Der Code ist derselbe, und er ist richtig. Was ist zu Ende gegangen?

Die Idee

Was ein Aufruf kostet

Jeder Aufruf bekommt eigenen Speicher auf dem Stack. Er heißt Frame (Stack Frame) und enthält drei Dinge:

  • die Parameter: hier category, die Kategorie, die dieser Aufruf zählt;
  • die lokalen Variablen: total und child, wie weit die Schleife ist;
  • den Rücksprungpunkt: welche Zeile des Aufrufers weitermacht, wenn dieser Aufruf fertig ist.

Der Frame lebt, bis der Aufruf zurückkehrt. Dann wird er weggeworfen, und sein Platz wird wiederverwendet. Die Zahl der gleichzeitig lebenden Frames ist die Tiefe der Rekursion. Sie ist nicht die Zahl der Aufrufe: Der Durchlauf ruft count_products 6-mal auf, aber es gibt höchstens 3 Frames gleichzeitig.

In der Lektion zur Rekursion hast du den Stapel von Frames für die Fakultät schon gesehen. Jeder Aufruf hat sein eigenes n und wartet auf die Antwort des Aufrufs über ihm:

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)




print(factorial(3))  # 6
Schritt für Schritt, in Worten
  1. Das Programm ruft factorial(3) auf.
  2. Neuer Speicher für factorial mit n = 3.
  3. 3 ist nicht 1, also ruft die Funktion factorial(2) auf und wartet auf die Antwort.
  4. Dasselbe noch einmal: factorial(2) ruft factorial(1) auf. Jeder Aufruf hat sein eigenes n.
  5. n ist 1: Das ist der Basisfall. Er gibt 1 zurück, ohne sich noch einmal aufzurufen.
  6. Die Antwort geht nach unten zurück: 2 * 1 = 2.
  7. Und noch einmal: 3 * 2 = 6.
  8. factorial(3) gibt 6 zurück, und das Programm gibt es aus.

Sieh es dir an

Die Frames des Durchlaufs

Jetzt dasselbe mit dem Shop-Baum. Sieh dir die Plätze jedes Frames an und die Zeile, auf die der Frame darunter wartet:

def count_products(category):
    total = category.products
    for child in category.children:
        total += count_products(child)
    return total


print("Produkte: " + str(count_products(shop)))
Schritt für Schritt, in Worten
  1. Das Programm ruft count_products(shop) auf. Bisher liegt auf dem Stack nur der Frame des Programms.
  2. Ein neuer Frame: der Parameter category = Shop, die lokale Variable total = 0 und der Rücksprungpunkt, wohin es zurückgeht, wenn der Aufruf endet.
  3. Die Schleife erreicht child = Elektronik und ruft sich selbst auf. Der Frame von Shop bleibt in Zeile 4 stehen und wartet; der neue Frame merkt sich diese Zeile.
  4. Smartphones hat keine Unterkategorien: Die Schleife läuft nicht. Das ist der Basisfall. 3 Frames des Durchlaufs leben gleichzeitig: Die Tiefe ist 3.
  5. return 5: Der Frame wird weggeworfen. Elektronik macht ab Zeile 4 weiter: total = 2 + 5 = 7.
  6. Laptops nimmt denselben Platz auf dem Stack ein und liefert 3. total = 7 + 3 = 10.
  7. Elektronik liefert 10. Der Frame von Shop wacht dort auf, wo er stehen geblieben ist: total = 10.
  8. Das nächste Kind: Haushalt, dann Küche. Wieder 3 Frames, an denselben Plätzen.
  9. Küche liefert 6, Haushalt liefert 4 + 6 = 10, und Shop kommt auf 10 + 10 = 20.
  10. 20 Produkte. 6 Aufrufe, aber nie mehr als 3 Frames des Durchlaufs gleichzeitig: Der Stack wächst mit der Tiefe des Baums, nicht mit der Zahl der Kategorien.

Wenn „Smartphones“ zurückkehrt, verschwindet sein Frame, und „Laptops“ nimmt denselben Platz. Der Speicher des Durchlaufs wächst mit dem längsten Pfad im Baum, nicht mit der Zahl der Kategorien. Bei einer Kette von 100.000 Kategorien ist der längste Pfad 100.000.

Probier es aus

Wie viele Frames gleichzeitig?

Hier zählt count_products, wie viele seiner Frames leben (depth), und merkt sich den größten Wert (deepest). Der Baum ist derselbe: Shop, Elektronik mit Smartphones und Laptops, Haushalt mit Küche.

depth = 0
deepest = 0




def count_products(category):
    global depth, deepest
    depth += 1
    deepest = max(deepest, depth)
    total = category.products
    for child in category.children:
        total += count_products(child)
    depth -= 1
    return total




total = count_products(shop)
print(f"{total} Produkte, höchstens {deepest} Frames gleichzeitig")
Antwort

Die Idee

Warum der Stack zu Ende ist

Der Stack ist ein eigener Speicherblock pro Thread, und er wächst nicht von allein: In Java, C# und Node liegt er in der Größenordnung von 1 MB, und Python zählt Frames und hält bei 1000 an. Ein Frame ist klein, zehn bis hundert Bytes, aber die Kette aus dem Import braucht 100.000 Frames gleichzeitig. chain(n) baut so eine Kette: n Kategorien, jede in der vorigen, je ein Produkt.

print("Die Grenze von Python:", sys.getrecursionlimit())
print(f"Tiefe 900: {count_products(chain(900))} Produkte")
try:
    print(f"Tiefe 100000: {count_products(chain(100_000))} Produkte")
except RecursionError as e:
    print(f"Tiefe 100000: RecursionError: {e}")
Ausgabe
Die Grenze von Python: 1000
Tiefe 900: 900 Produkte
Tiefe 100000: RecursionError: maximum recursion depth exceeded
Python hält schon bei 1000 Frames an, lange bevor der echte Stack zu Ende ist. Das ist eine Sicherung, nicht das Ende des Speichers: 900 Ebenen gehen durch, 1000 nicht.

Der Speicher, den der Durchlauf braucht, ist O(Tiefe), wie in der Lektion „Speicherkomplexität“. In einem ausgeglichenen Baum ist die Tiefe klein. In einer Kette ist sie n.

Sieh es dir an

Der Fehler fällt durch jeden Frame

Der Überlauf geschieht im obersten Frame, 100.000 Ebenen weiter oben. Von dort fällt der Fehler wie jede Exception: Ein Frame ohne catch wird weggeworfen, und der Fehler geht weiter nach unten. So fiel die Exception beim Geldabheben in der Lektion „Werfen und eigene Exceptions“ durch die Frames:

def withdraw(self, amount):
    if amount > self.balance:
        raise ValueError("Nicht genug Geld")
    self.balance -= amount




def pay_rent(account):
    account.withdraw(800)
    print("Die Miete ist bezahlt.")




try:
    pay_rent(Account(500))
except ValueError as e:
    print(f"Abgelehnt: {e}")
Schritt für Schritt, in Worten
  1. Das Programm ruft pay_rent für ein Konto mit 500 € auf.
  2. pay_rent ruft withdraw(800) auf: ein neuer Frame oben drauf.
  3. 800 > 500: Die Methode wirft mit raise eine Exception.
  4. Der Kontostand ändert sich nicht: Der Frame wird verworfen, ohne seine Zeilen zu Ende auszuführen.
  5. pay_rent hat kein except: „Die Miete ist bezahlt.“ wird nicht ausgegeben, und der Frame wird verworfen.
  6. Das except im Programm fängt die Exception, und das Programm macht hier weiter.

Wenn der Fehler catch erreicht, sind alle 100.000 Frames schon weg, und der Stack ist wieder leer. Deshalb macht das Programm oben weiter und gibt aus.

Die Idee

Der Kreis: Der Basisfall kommt nie

Wo ist der Basisfall von count_products? Es gibt kein if. Der Basisfall ist eine Kategorie ohne Unterkategorien: Die Schleife läuft kein einziges Mal, und die Funktion liefert ihre eigenen Produkte zurück.

Der zweite Import hat „Haushalt“ in die eigene „Küche“ gesetzt. Jetzt hat der Pfad Shop → Haushalt → Küche → Haushalt → Küche → … kein Ende. Jede Kategorie darauf hat eine Unterkategorie, also kommt der Basisfall nie:

kitchen.add(home)
try:
    print("Produkte: " + str(count_products(shop)))
except RecursionError as e:
    print(f"Mit dem Kreis: RecursionError: {e}")
Ausgabe
Mit dem Kreis: RecursionError: maximum recursion depth exceeded

Das ist ein Basisfall, der nie erreicht wird. Er steht im Code, aber die Eingabe führt nie zu ihm. Der Baum kommt von außen (ein Import, eine API, eine Datenbank), also muss der Durchlauf sowohl einen tiefen als auch einen kreisförmigen Baum überleben. Wie, steht in der nächsten Lektion, „Von der Rekursion zur Schleife“.

Die Idee

Zwei Basisfälle

Manchmal gibt es mehr als einen Grund aufzuhören. find sucht eine Kategorie nach Namen und hat zwei Basisfälle:

  • gefunden: Der Name passt, und die Funktion liefert die Kategorie zurück, ohne weiter nach unten zu gehen;
  • weiter unten nichts: Keine Unterkategorie enthält sie, und die Funktion liefert None zurück.
def find(category, name):
    if category.name == name:
        return category
    for child in category.children:
        found = find(child, name)
        if found is not None:
            return found
    return None




for name in ["Küche", "Garten"]:
    found = find(shop, name)
    if found is None:
        print(name + ": keine solche Kategorie")
    else:
        print(f"{name}: {found.products} Produkte")
Ausgabe
Küche: 6 Produkte
Garten: keine solche Kategorie

Sobald ein Kind die Kategorie findet, geht die Antwort direkt durch alle Frames zurück nach oben, ohne die anderen Kinder zu durchlaufen.

Probier es aus

Ergänze

Was liefert find zurück, wenn die Kategorie in keinem der Teilbäume liegt?

def find(category, name):
    if category.name == name:
        return category
    for child in category.children:
        found = find(child, name)
        if found is not None:
            return found
    return

Probier es aus

Finde den Fehler

Der Shop verkauft auf Raten. months(150, 50) liefert 3 Monate. months(130, 50) sollte auch 3 liefern (50 €, 50 € und 30 €), aber es bricht mit RecursionError ab. Welche Zeile ist falsch?

Wähle die Zeile mit dem Fehler.

Übung

Der Brotkrumenpfad

Löse die Aufgabe in deinem Editor.

Der Pfad zur Kategorie. Über den Produkten zeigt der Shop den Pfad zur Kategorie: „Shop > Haushalt > Küche“. Schreibe eine rekursive Funktion path(category, name), die die Liste der Namen von der Wurzel bis zur gesuchten Kategorie liefert, oder None, wenn sie nicht da ist. Die zwei Basisfälle sind wie bei find. Lies den Namen und gib den Pfad aus.

Eingabe
Küche
Ausgabe
Shop > Haushalt > Küche

Bei der Eingabe Garten lautet die Ausgabe Keine solche Kategorie.

Weitere Aufgaben

  • Die tiefste Kategorie. Schreibe eine rekursive depth(category): Eine Kategorie ohne Kinder hat die Tiefe 1, sonst ist es 1 + das tiefste Kind. Für den Baum der Lektion ist es 3, für die Kette aus dem Import 100.000.
  • Die Raten. Korrigiere months und lass es mit 130 und 50 laufen, dann mit 0 und 50. Wie viele Frames öffnet jeder Aufruf?

Genauer

Wie groß der Stack ist

Der Stack ist nicht endlos, und er ist nicht überall gleich. Die Zahlen unten sind Standardwerte, und sie lassen sich ändern.

Genauer, für Neugierige

Die Größe. In Python ist die Grenze eine Zahl von Frames: sys.getrecursionlimit() ist 1000. sys.setrecursionlimit(100_000) hebt die Grenze an, aber nicht den echten Stack des Prozesses: Bei tief genug verschachtelter Rekursion stürzt Python ohne Meldung ab. Um wirklich mehr Platz zu bekommen, brauchst du einen Thread mit größerem Stack (threading.stack_size), und selbst dann kann die Kette aus dem Import tiefer sein.

Die Größe eines Frames. Wie viele Frames hineinpassen, hängt vom Frame ab: Mehr Parameter und lokale Variablen sind mehr Bytes. Deshalb ist in Node die Zahl der Aufrufe vor dem Überlauf keine genaue Zahl, in Python dagegen schon, weil Python Frames zählt.

Der Baum und der Objektspeicher. Die Kategorien selbst liegen nicht auf dem Stack. Sie sind Objekte im Objektspeicher (dem Heap), und ein Frame hält nur eine Referenz auf eines davon. Deshalb passen 100.000 Kategorien problemlos in den Speicher, 100.000 Frames gleichzeitig aber nicht.

Die Rückkehr. Der Rücksprungpunkt ist die Adresse der Anweisung, an der der Aufrufer weitermacht. Im Prozessor ist das buchstäblich eine Adresse im Speicher, in den Frame geschrieben. Die Szene zeigt sie als Zeilennummer.

Test

Teste dich

1. Was enthält der Frame des Aufrufs für die Kategorie „Haushalt“?
2. Der Katalog hat 1000 Kategorien, und der längste Pfad von „Shop“ zur tiefsten ist 4 Kategorien lang. Wie viele Frames des Durchlaufs gibt es höchstens gleichzeitig?
3. „Haushalt“ wurde aus Versehen unter die eigene „Küche“ gesetzt. Warum läuft der Stack beim Durchlauf über, statt eine falsche Summe zu liefern?
4. months(130, 50) sollte 3 liefern, läuft aber über den Stack. Warum?
5. Was misst die Grenze in Python, und was misst die Stackgrenze in Java, C# und JavaScript?

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