Der Aufrufstapel von innen

Code in:JavaC#PythonJavaScript

Kurz gesagt: Der Aufrufstapel hält für jeden Aufruf, der noch nicht fertig ist, einen Frame; geht die Rekursion zu tief, ist er zu Ende, und das Programm scheitert mit StackOverflowError.

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 Methode zählt sie, wie in der Lektion „Rekursion“:

static int countProducts(Category category) {
    int total = category.products;
    for (Category child : category.children) {
        total += countProducts(child);
    }
    return total;
}

Category phones = new Category("Smartphones", 5);
Category laptops = new Category("Laptops", 3);
Category electronics = new Category("Elektronik", 2).add(phones, laptops);
Category kitchen = new Category("Küche", 6);
Category home = new Category("Haushalt", 4).add(kitchen);
Category shop = new Category("Shop", 0).add(electronics, home);
System.out.println("Produkte: " + countProducts(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 StackOverflowError.

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 countProducts 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:

static int factorial(int n) {
    if (n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

System.out.println(factorial(3));  // 6

Schritt für Schritt, in Worten

1. main ruft factorial(3) auf.
2. Neuer Speicher für factorial mit n = 3.
3. 3 ist nicht 1, also ruft die Methode 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 main 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:

static int countProducts(Category category) {
    int total = category.products;
    for (Category child : category.children) {
        total += countProducts(child);
    }
    return total;
}

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

Schritt für Schritt, in Worten

1. main ruft countProducts(shop) auf. Bisher liegt auf dem Stack nur der Frame von main.
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 countProducts, 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.

static int depth = 0;
static int deepest = 0;

static int countProducts(Category category) {
    depth++;
    deepest = Math.max(deepest, depth);
    int total = category.products;
    for (Category child : category.children) {
        total += countProducts(child);
    }
    depth--;
    return total;
}

int total = countProducts(shop);
System.out.println(total + " Produkte, höchstens " + deepest + " Frames gleichzeitig");

Antwort

20 Produkte, höchstens 2 Frames gleichzeitig

20 Produkte, höchstens 6 Frames gleichzeitig

20 Produkte, höchstens 3 Frames gleichzeitig

Prüfen

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.

Category small = chain(900);
System.out.println("Tiefe 900: " + countProducts(small) + " Produkte");
Category deep = chain(100_000);
Thread worker = new Thread(null, () -> {
    try {
        System.out.println("Tiefe 100000: " + countProducts(deep) + " Produkte");
    } catch (StackOverflowError e) {
        System.out.println("Tiefe 100000: " + e);
    }
}, "catalog", 1024 * 1024);
worker.start();
worker.join();

Ausgabe

Tiefe 900: 900 Produkte
Tiefe 100000: java.lang.StackOverflowError

StackOverflowError ist ein Error, keine Exception. Hier läuft der Durchlauf in einem Thread mit 1-MB-Stack (das vierte Argument von new Thread), damit er sich auf jedem Rechner gleich verhält. 900 Ebenen gehen durch, 100.000 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:

public void withdraw(int amount) {
    if (amount > balance) {
        throw new IllegalArgumentException("Nicht genug Geld");
    }
    balance -= amount;
}
static void payRent(Account account) {
    account.withdraw(800);
    System.out.println("Die Miete ist bezahlt.");
}

try {
    payRent(new Account(500));
} catch (IllegalArgumentException e) {
    System.out.println("Abgelehnt: " + e.getMessage());
}

Schritt für Schritt, in Worten

1. main ruft payRent für ein Konto mit 500 € auf.
2. payRent ruft withdraw(800) auf: ein neuer Frame oben drauf.
3. 800 > 500: Die Methode wirft eine Exception.
4. Der Kontostand ändert sich nicht: Der Frame wird verworfen, ohne seine Zeilen zu Ende auszuführen.
5. payRent hat kein catch: „Die Miete ist bezahlt.“ wird nicht ausgegeben, und der Frame wird verworfen.
6. Das catch in main 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 countProducts? Es gibt kein if. Der Basisfall ist eine Kategorie ohne Unterkategorien: Die Schleife läuft kein einziges Mal, und die Methode 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 {
    System.out.println("Produkte: " + countProducts(shop));
} catch (StackOverflowError e) {
    System.out.println("Mit dem Kreis: " + e);
}

Ausgabe

Mit dem Kreis: java.lang.StackOverflowError

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 Methode liefert die Kategorie zurück, ohne weiter nach unten zu gehen;
• weiter unten nichts: Keine Unterkategorie enthält sie, und die Methode liefert null zurück.

static Category find(Category category, String name) {
    if (category.name.equals(name)) {
        return category;
    }
    for (Category child : category.children) {
        Category found = find(child, name);
        if (found != null) {
            return found;
        }
    }
    return null;
}

for (String name : List.of("Küche", "Garten")) {
    Category found = find(shop, name);
    if (found == null) {
        System.out.println(name + ": keine solche Kategorie");
    } else {
        System.out.println(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?

static Category find(Category category, String name) {
    if (category.name.equals(name)) {
        return category;
    }
    for (Category child : category.children) {
        Category found = find(child, name);
        if (found != null) {
            return found;
        }
    }
    return ;
}

Prüfen

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 StackOverflowError ab. Welche Zeile ist falsch?

Wähle die Zeile mit dem Fehler.

1static int months(int debt, int payment) {2 if (debt == 0) {3 return 0;4 }5 return 1 + months(debt - payment, payment);6}

Prüfen

Ü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 Methode path(category, name), die die Liste der Namen von der Wurzel bis zur gesuchten Kategorie liefert, oder null, 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 Java hat jeder Thread seinen eigenen Stack. Die Standardgröße wird mit -Xss festgelegt: 1 MB auf x64, 2 MB auf 64-Bit-ARM unter Linux, und ein neuer Thread kann seine eigene als viertes Argument von new Thread bekommen, wie im Programm oben. Die Prüfung der Seite startet Programme mit -Xss8m, deshalb läuft der Durchlauf hier in einem Thread mit 1 MB.

Die Größe eines Frames. Wie viele Frames hineinpassen, hängt vom Frame ab: Mehr Parameter und lokale Variablen sind mehr Bytes. Der JIT-Compiler kann einen Frame kleiner machen, also ist die Zahl der Aufrufe vor dem Überlauf keine genaue Zahl und ändert sich zwischen den Läufen.

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“?

Den ganzen KategorienbaumNur das Ergebnis, das er zurückgeben wirdDen Parameter category, die lokalen Variablen total und child und die Stelle, an der der Frame darunter weitermacht

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?

1010004

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?

Der Baum wird zu breitAuf dem Pfad um den Kreis hat jede Kategorie eine Unterkategorie, also kommt der Basisfall (eine Kategorie ohne Kinder) nieDie Summe wird größer als int

4. months(130, 50) sollte 3 liefern, läuft aber über den Stack. Warum?

Die Schuld geht 80, 30, −20, −70 … und ist nie genau 0Die Rekursion ist für 130 zu tiefpayment wird nicht kleiner

5. Was misst die Grenze in Python, und was misst die Stackgrenze in Java, C# und JavaScript?

Python zählt Frames (1000), die anderen messen Bytes an Speicher, also hängt die Zahl der Aufrufe von der Größe eines Frames abBeide messen BytesBeide zählen Frames

Prüfen

Lektion von vorn beginnen

Verwandte Lektionen

• Baut auf: Lambdas · Threads · Big-O: wie die Arbeit wächst · Speicherkomplexität
• Geht weiter in: Von der Rekursion zur Schleife · Schnelles Potenzieren · Binärer Suchbaum · DFS: Inseln und Zyklen
• Aufgaben zum Thema: Rekursion