Von der Rekursion zur Iteration in C#: Endrekursion

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:

var last = Chain(100_000);
while (last.Children.Count > 0)
{
    last = last.Children[0];
}
var worker = new Thread(() =>
{
    try
    {
        Console.WriteLine("Rekursion: Ebene " + LevelOf(last, 0));
    }
    catch (InsufficientExecutionStackException e)
    {
        Console.WriteLine("Rekursion: " + e.GetType().Name);
    }
}, 1024 * 1024);
worker.Start();
worker.Join();
Console.WriteLine("Schleife: Ebene " + LevelOfLoop(last));

Rekursion: InsufficientExecutionStackException
Schleife: Ebene 99999

Die Rekursion läuft in einem Thread mit 1-MB-Stack, und LevelOf hat die Sicherung aus der vorigen Lektion, RuntimeHelpers.EnsureSufficientExecutionStack(): Ein echter Überlauf würde den Prozess töten.

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;
    var stack = new Stack<Category>();
    stack.Push(root);
    while (stack.Count > 0)
    {
        Category category = stack.Pop();
        total += category.Products;
        foreach (Category child in category.Children)
        {
            stack.Push(child);
        }
    }
    return total;
}

Console.WriteLine("Produkte: " + CountProducts(shop));

Produkte: 20

Stack<T>: 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;
    var stack = new Stack<Category>();
    stack.Push(root);
    while (stack.Count > 0)
    {
        Category category = stack.Pop();
        total += category.Products;
        foreach (Category child in category.Children)
        {
            stack.Push(child);
        }
    }
    return total;
}

Console.WriteLine("Produkte: " + CountProducts(shop));

Schritt für Schritt, in Worten

Der Stack ist ein Stack<Category> im Objektspeicher (Heap), nicht der Aufrufstapel. Zuerst kommt die Wurzel hinein.
pop nimmt das oberste: Shop. Seine Kinder kommen obenauf: Elektronik, dann Haushalt.
Als Nächstes kommt Haushalt, nicht Elektronik: Ein Stack gibt das zuletzt Hineingelegte zurück. total = 4, und Küche kommt hinein.
Küche hat keine Kinder: Es kommt nichts hinein. total = 10.
Erst jetzt Elektronik: total = 12. Smartphones und Laptops kommen hinein.
Laptops (15), dann Smartphones (20).
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)
{
    var stack = new Stack<Category>();
    stack.Push(root);
    while (stack.Count > 0)
    {
        Category category = stack.Pop();
        Console.WriteLine(category.Name);
        foreach (Category child in category.Children)
        {
            stack.Push(child);
        }
    }
}

PrintOrder(shop);

Antwort

Shop
Elektronik
Haushalt
Smartphones
Laptops
Küche

Shop
Haushalt
Küche
Elektronik
Laptops
Smartphones

Shop
Elektronik
Smartphones
Laptops
Haushalt
Küche

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)
{
    var stack = new Stack<(Category Category, int Level)>();
    stack.Push((root, 0));
    while (stack.Count > 0)
    {
        var (category, level) = stack.Pop();
        Console.WriteLine(new string(' ', 2 * level) + category.Name);
        for (int i = category.Children.Count - 1; i >= 0; i--)
        {
            stack.Push((category.Children[i], level + 1));
        }
    }
}

PrintMenu(shop);

Shop
  Elektronik
    Smartphones
    Laptops
  Haushalt
    Küche

Der Stack hält Tupel (Category, int). Die for-Schleife läuft von hinten. Vorsicht bei category.Children.Reverse(): Bei List<T> ist das die Methode, die die Liste selbst an Ort und Stelle umkehrt und nichts zurückgibt, und das Menü wäre für immer umgekehrt.

Sieh es dir an

Der tiefe Baum kommt durch

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

var deep = Chain(100_000);
Console.WriteLine($"Tiefe 100000: {CountProducts(deep)} Produkte");

Tiefe 100000: 100000 Produkte

In allen vier Sprachen, und in C# ohne Sicherung, 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;
    var seen = new HashSet<Category>();
    var stack = new Stack<Category>();
    stack.Push(root);
    while (stack.Count > 0)
    {
        Category category = stack.Pop();
        if (!seen.Add(category))
        {
            Console.WriteLine("Ich überspringe " + category.Name + ": schon besucht");
            continue;
        }
        total += category.Products;
        foreach (Category child in category.Children)
        {
            stack.Push(child);
        }
    }
    return total;
}

kitchen.Add(home);
Console.WriteLine("Produkte: " + CountProducts(shop));

Ich überspringe Haushalt: schon besucht
Produkte: 20

seen.Add liefert false, wenn die Kategorie schon darin ist: eine Prüfung statt zwei. Category ist eine Klasse ohne Equals, 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:

{
foreach (Category child in category.Children)
}
{
static int CountProducts(Category root)
stack.Push(child);
var stack = new Stack<Category>();
int total = 0;
return total;
}
}
Category category = stack.Pop();
while (stack.Count > 0)
stack.Push(root);
total += category.Products;
{

Probier es aus

Ergänze

Wann hört die Schleife auf?

static int CountProducts(Category root)
{
    int total = 0;
    var stack = new Stack<Category>();
    stack.Push(root);
    while ()
    {
        Category category = stack.Pop();
        total += category.Products;
        foreach (Category child in 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ü.

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

C#: Stack<T> ist innen ein Array, das sich verdoppelt, wenn es voll wird. Queue<T> ist dasselbe für eine Queue.
new Thread(work, 64 * 1024 * 1024) gibt einem Thread einen großen Stack und 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?return 1 + Months(debt - payment, payment);return LevelOf(category.parent, level + 1);total += CountProducts(child);

Ein Endaufruf ist ein Aufruf, nach dem nichts mehr zu tun bleibt: Sein Ergebnis wird direkt zurückgegeben. Bei total += und bei 1 + hat der Aufrufer noch Arbeit, also wird sein Frame gebraucht.

2. Welche der vier Sprachen verwandelt Endrekursion in eine Schleife, sodass der Stack nicht wächst?Nur PythonIn der Praxis keine: Java, C# und Python tun es nicht, und der JavaScript-Standard verlangt es, aber V8 (Node, Chrome) tut es nichtAlle, wenn der Aufruf der letzte ist

3. Warum kommt der Durchlauf mit eigenem Stack durch die Kette von 100.000 Ebenen, die Rekursion aber nicht?Der eigene Stack ist ein Objekt im Objektspeicher und wächst nach Bedarf, während die Funktion einen einzigen Frame hatDer eigene Stack hält immer nur eine KategorieDie Schleife macht weniger Operationen

4. Die Kinder einer Kategorie kommen in ihrer Reihenfolge in deinen eigenen Stack: Smartphones, dann Laptops. Was kommt zuerst heraus?Das hängt von der Sprache abLaptops: Ein Stack gibt das zuletzt Hineingelegte zurückSmartphones: Es ist das erste

5. Was passiert, wenn der Durchlauf mit eigenem Stack auf einen Kreis trifft (Haushalt → Küche → Haushalt) und sich die gesehenen Kategorien nicht merkt?Er liefert eine falsche Summe und hört aufEr wirft StackOverflowErrorEr dreht sich ewig, ohne Fehler: Haushalt und Küche wechseln sich im Stack ab

Von der Rekursion zur Schleife

Cookies