Стекът от извиквания отвътре

Код на:JavaC#PythonJavaScript

Накратко: Стекът от извиквания пази по една рамка за всяко незавършило извикване; при твърде дълбока рекурсия той свършва и процесът пада със StackOverflowException.

Проблем

Каталогът, който събаря страницата

Менюто на онлайн магазина е дърво: категории, в тях подкатегории, във всяка по няколко продукта. До името пише колко продукта има заедно с подкатегориите: „Електроника (10)“. Брои ги рекурсивна метод, както в урока „Рекурсия“:

static int CountProducts(Category category)
{
    int total = category.Products;
    foreach (Category child in category.Children)
    {
        total += CountProducts(child);
    }
    return total;
}

var phones = new Category("Телефони", 5);
var laptops = new Category("Лаптопи", 3);
var electronics = new Category("Електроника", 2).Add(phones, laptops);
var kitchen = new Category("Кухня", 6);
var home = new Category("Дом", 4).Add(kitchen);
var shop = new Category("Магазин", 0).Add(electronics, home);
Console.WriteLine("Продукти: " + CountProducts(shop));

Изход

Продукти: 20

Месеци наред работи. После идват два нови импорта от доставчици. Първият слага всяка нова категория вътре в предишната: веригата е дълбока 100 000 нива. Вторият по погрешка слага „Дом“ в собствената му подкатегория „Кухня“. И в двата случая страницата пада с Stack overflow. и процесът на сървъра умира.

Кодът е същият и е верен. Какво свърши?

Идеята

Какво струва едно извикване

Всяко извикване получава своя памет в стека. Тя се казва рамка (stack frame) и пази три неща:

• параметрите: тук category, категорията, която това извикване брои;
• локалните променливи: total и child, докъде е стигнал цикълът;
• мястото за връщане: кой ред от извикващия да продължи, когато това извикване свърши.

Рамката живее, докато извикването не върне. Тогава се изхвърля и мястото ѝ се ползва наново. Броят рамки, живи наведнъж, е дълбочината на рекурсията. Тя е различна от броя извиквания: обходът вика CountProducts 6 пъти, а рамките наведнъж са най-много 3.

В урока за рекурсията вече видя купчината от рамки при факториела. Всяко извикване има свое n и чака отговора на онова над него:

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

Console.WriteLine(Factorial(3));  // 6

Стъпка по стъпка, с думи

1. Main вика Factorial(3).
2. Нова памет за Factorial с n = 3.
3. 3 не е 1, затова методът вика Factorial(2) и чака отговора.
4. Същото: Factorial(2) вика Factorial(1). Всяко извикване има свое n.
5. n е 1: това е дъното. Връща 1, без да вика повече.
6. Отговорът слиза надолу: 2 * 1 = 2.
7. И пак: 3 * 2 = 6.
8. Factorial(3) връща 6 и Main го отпечатва.

Виж го

Рамките на обхода

Сега същото с дървото на магазина. Гледай гнездата на всяка рамка и реда, на който рамката отдолу чака:

static int CountProducts(Category category)
{
    int total = category.Products;
    foreach (Category child in category.Children)
    {
        total += CountProducts(child);
    }
    return total;
}

Console.WriteLine("Продукти: " + CountProducts(shop));

Стъпка по стъпка, с думи

1. Main вика CountProducts(shop). Засега в стека е само рамката на Main.
2. Нова рамка: параметърът category = Магазин, локалната total = 0 и мястото за връщане: къде да продължи, когато свърши.
3. Цикълът стига до child = Електроника и вика себе си. Рамката на Магазин спира на ред 6 и чака; новата рамка помни този ред.
4. Телефони няма подкатегории: цикълът не се върти. Това е дъното. Живи са 3 рамки на обхода наведнъж: дълбочината е 3.
5. return 5: рамката се изхвърля. Електроника продължава от ред 6: total = 2 + 5 = 7.
6. Лаптопи заема същото място в стека и връща 3. total = 7 + 3 = 10.
7. Електроника връща 10. Рамката на Магазин се събужда там, където спря: total = 10.
8. Следващото дете: Дом, после Кухня. Пак 3 рамки, на същите места.
9. Кухня връща 6, Дом връща 4 + 6 = 10, а Магазин стига до 10 + 10 = 20.
10. 20 продукта. 6 извиквания, но никога повече от 3 рамки на обхода наведнъж: стекът расте с дълбочината на дървото, не с броя категории.

Когато „Телефони“ върне, рамката ѝ изчезва, а „Лаптопи“ заема същото място. Паметта на обхода расте с най-дългия път в дървото, не с броя категории. При верига от 100 000 категории най-дългият път е 100 000.

Пробвай

Колко рамки наведнъж?

Тук CountProducts брои колко свои рамки са живи (depth) и помни най-голямото (deepest). Дървото е същото: Магазин, Електроника с Телефони и Лаптопи, Дом с Кухня.

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

static int CountProducts(Category category)
{
    depth++;
    deepest = Math.Max(deepest, depth);
    int total = category.Products;
    foreach (Category child in category.Children)
    {
        total += CountProducts(child);
    }
    depth--;
    return total;
}

int total = CountProducts(shop);
Console.WriteLine($"{total} продукта, най-много {deepest} рамки наведнъж");

Отговор

20 продукта, най-много 3 рамки наведнъж

20 продукта, най-много 2 рамки наведнъж

20 продукта, най-много 6 рамки наведнъж

Провери

Идеята

Защо стекът свършва

Стекът е отделен блок памет за всяка нишка и не расте сам: в Java, C# и Node е от порядъка на 1 MB, а Python брои рамките и спира при 1000. Една рамка е малка, десетки до стотина байта, но веригата от импорта иска 100 000 рамки наведнъж. chain(n) строи такава верига: n категории, всяка вътре в предишната, по един продукт.

var small = Chain(900);
Console.WriteLine($"Дълбочина 900: {CountProducts(small)} продукта");
var deep = Chain(100_000);
var worker = new Thread(() =>
{
    try
    {
        Console.WriteLine($"Дълбочина 100000: {CountProducts(deep)} продукта");
    }
    catch (InsufficientExecutionStackException e)
    {
        Console.WriteLine("Дълбочина 100000: " + e.GetType().Name);
    }
}, 1024 * 1024);
worker.Start();
worker.Join();

Изход

Дълбочина 900: 900 продукта
Дълбочина 100000: InsufficientExecutionStackException

В C# истинското препълване не може да се хване: процесът печата Stack overflow., списък от рамките и спира, заедно с целия сървър. Няма catch, който да го спаси. Затова програмата горе не го пуска истински. Първият ред на CountProducts е предпазител: RuntimeHelpers.EnsureSufficientExecutionStack() хвърля InsufficientExecutionStackException, когато стекът е почти пълен, а това изключение вече се хваща. Обходът върви в нишка със стек от 1 MB (вторият аргумент на new Thread), за да е еднакво на всяка машина: в Linux главната нишка има 8 MB и щеше да събере повече нива.

static int CountProducts(Category category)
{
    RuntimeHelpers.EnsureSufficientExecutionStack();
    int total = category.Products;
    foreach (Category child in category.Children)
    {
        total += CountProducts(child);
    }
    return total;
}

Паметта, която обходът иска, е O(дълбочината), както в урока „Сложност по памет“. При балансирано дърво дълбочината е малка. При верига тя е n.

Виж го

Грешката пада през всички рамки

Препълването се случва в най-горната рамка, 100 000 нива нагоре. Предпазителят хвърля InsufficientExecutionStackException и то пада като всяко изключение: рамка без catch се изхвърля и изключението продължава надолу. Така изключението от теглене на пари падаше през рамките в урока „Хвърляне на изключения“:

public void Withdraw(int amount)
{
    if (amount > Balance)
    {
        throw new ArgumentException("Не стигат парите");
    }
    Balance -= amount;
}
static void PayRent(Account account)
{
    account.Withdraw(800);
    Console.WriteLine("Наемът е платен.");
}

try
{
    PayRent(new Account(500));
}
catch (ArgumentException e)
{
    Console.WriteLine("Отказано: " + e.Message);
}

Стъпка по стъпка, с думи

1. Main вика PayRent за сметка с 500 €.
2. PayRent вика Withdraw(800): нова рамка отгоре.
3. 800 > 500: методът хвърля изключение.
4. Балансът не се променя: рамката се изхвърля, без да довърши редовете си.
5. PayRent няма catch: „Наемът е платен.“ не се печата, рамката се изхвърля.
6. catch в Main хваща изключението и програмата продължава оттук.

Когато грешката стигне catch, всичките 100 000 рамки вече ги няма и стекът пак е празен. Затова програмата отгоре продължава и печата. При истинското StackOverflowException такова падане няма: процесът спира на място.

Идеята

Кръгът: дъното не идва

Къде е дъното на CountProducts? Няма if. Дъното е категория без подкатегории: цикълът не се върти нито веднъж и методът връща собствените си продукти.

Вторият импорт сложи „Дом“ в собствената му „Кухня“. Сега пътят Магазин → Дом → Кухня → Дом → Кухня → … няма край. Всяка категория по него има подкатегория, затова дъното не идва:

kitchen.Add(home);
try
{
    Console.WriteLine("Продукти: " + CountProducts(shop));
}
catch (InsufficientExecutionStackException e)
{
    Console.WriteLine("С кръг: " + e.GetType().Name);
}

Изход

С кръг: InsufficientExecutionStackException

Това е дъно, което не се стига. То е там в кода, но входът никога не го докарва. Дървото идва отвън (импорт, API, база), затова обходът трябва да оцелее и на дълбоко, и на кръгово дърво. Как, е в следващия урок, „От рекурсия към цикъл“.

Идеята

Две дъна

Понякога спирането има повече от една причина. Find търси категория по име и има две дъна:

• намерено: името съвпада, и методът връща категорията, без да слиза по-надолу;
• няма по-надолу: нито една подкатегория не я съдържа, и методът връща null.

static Category? Find(Category category, string name)
{
    if (category.Name == name)
    {
        return category;
    }
    foreach (Category child in category.Children)
    {
        Category? found = Find(child, name);
        if (found != null)
        {
            return found;
        }
    }
    return null;
}

foreach (string name in new[] { "Кухня", "Градина" })
{
    Category? found = Find(shop, name);
    if (found == null)
    {
        Console.WriteLine(name + ": няма такава категория");
    }
    else
    {
        Console.WriteLine($"{name}: {found.Products} продукта");
    }
}

Изход

Кухня: 6 продукта
Градина: няма такава категория

Щом някое дете намери категорията, отговорът се връща веднага нагоре, през всички рамки, без да обхожда останалите деца.

Пробвай

Попълни

Кое връща Find, когато категорията я няма в нито едно поддърво?

static Category? Find(Category category, string name)
{
    if (category.Name == name)
    {
        return category;
    }
    foreach (Category child in category.Children)
    {
        Category? found = Find(child, name);
        if (found != null)
        {
            return found;
        }
    }
    return ;
}

Провери

Пробвай

Намери грешката

Магазинът продава на вноски. Months(150, 50) връща 3 месеца. Months(130, 50) трябва също да върне 3 (50, 50 и 30 €), а убива процеса със Stack overflow.. На кой ред е грешката?

Избери реда с грешката.

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

Провери

Упражнение

Пътечката

Реши задачата в редактора си.

Пътечката до категорията. Над продуктите магазинът показва пътя до категорията: „Магазин > Дом > Кухня“. Напиши рекурсивна метод Path(category, name), която връща списъка с имената от корена до търсената категория, или null, ако я няма. Двете дъна са като при Find. Прочети името и отпечатай пътя.

Вход

Кухня

Изход

Магазин > Дом > Кухня

С вход Градина изходът е Няма такава категория.

Още задачи

• Най-дълбоката категория. Напиши рекурсивна Depth(category): категория без деца е на дълбочина 1, а иначе е 1 + най-дълбокото дете. За дървото от урока е 3, за веригата от импорта е 100 000.
• Вноските. Поправи Months и я пусни с 130 и 50, после с 0 и 50. Колко рамки отваря всяко извикване?

По-точно

Колко голям е стекът

Стекът не е безкраен и не е еднакъв навсякъде. Числата по-долу са по подразбиране и се сменят.

По-точно, за любопитните

Размерът. В .NET главната нишка има около 1 MB под Windows, а под Linux колкото даде системата, обикновено 8 MB. new Thread(work, maxStackSize) дава на нова нишка свой размер. EnsureSufficientExecutionStack гледа колко е останало в стека на текущата нишка, затова предпазителят работи при всеки размер.

Големината на рамката. Колко рамки се събират, зависи от рамката: повече параметри и локални променливи са повече байтове. JIT компилаторът може да направи рамката по-малка, затова броят извиквания до препълването не е точно число и се мени между пусканията.

Дървото и паметта на обектите. Самите категории не са в стека. Те са обекти в паметта за обекти (heap), а рамката пази само референция към една от тях. Затова 100 000 категории се събират в паметта без проблем, а 100 000 рамки наведнъж не.

Връщането. Мястото за връщане е адресът на инструкцията, от която продължава извикващият. На процесора това е буквално адрес в паметта, записан в рамката. Сцената го показва като номер на ред.

Тест

Провери се

1. Какво пази рамката на извикването за категорията „Дом“?

Параметъра category, локалните total и child и мястото, където продължава рамката отдолуСамо резултата, който ще върнеЦялото дърво от категории

2. Каталогът има 1000 категории, а най-дългият път от „Магазин“ до най-дълбоката е 4 категории. Колко рамки на обхода има най-много наведнъж?

1010004

3. „Дом“ по погрешка става подкатегория на своята „Кухня“. Защо обходът препълва стека, а не дава грешна сума?

Сумата става по-голяма от intДървото става твърде широкоПо пътя в кръга всяка категория има подкатегория, затова дъното (категория без деца) никога не идва

4. months(130, 50) трябва да върне 3, а препълва стека. Защо?

Дългът става 80, 30, −20, −70… и никога не е точно 0Рекурсията е твърде дълбока за 130payment не се смалява

5. Какво мери границата на Python и какво границата на стека в Java, C# и JavaScript?

И двете броят рамкиИ двете мерят байтовеPython брои рамките (1000), а другите мерят байтове памет, затова броят извиквания зависи от големината на рамката

Провери

Започни урока отначало

Свързани уроци

• Нужно отпреди: Ламбди и делегати · Нишки · Big-O: как расте работата · Сложност по памет
• Продължава в: От рекурсия към цикъл · Бързо степенуване · Двоично дърво за търсене · DFS: острови и кръгове
• Задачи по темата: Рекурсия