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

Код на:JavaC#PythonJavaScript

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

Проблем

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

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

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

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

Изход

Продукти: 20

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

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

Идеята

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

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

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

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

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

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

System.out.println(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;
    for (Category child : category.children) {
        total += countProducts(child);
    }
    return total;
}

System.out.println("Продукти: " + countProducts(shop));

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

1. main вика countProducts(shop). Засега в стека е само рамката на main.
2. Нова рамка: параметърът category = Магазин, локалната total = 0 и мястото за връщане: къде да продължи, когато свърши.
3. Цикълът стига до child = Електроника и вика себе си. Рамката на Магазин спира на ред 4 и чака; новата рамка помни този ред.
4. Телефони няма подкатегории: цикълът не се върти. Това е дъното. Живи са 3 рамки на обхода наведнъж: дълбочината е 3.
5. return 5: рамката се изхвърля. Електроника продължава от ред 4: 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;
    for (Category child : category.children) {
        total += countProducts(child);
    }
    depth--;
    return total;
}

int total = countProducts(shop);
System.out.println(total + " продукта, най-много " + deepest + " рамки наведнъж");

Отговор

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

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

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

Провери

Идеята

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

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

Category small = chain(900);
System.out.println("Дълбочина 900: " + countProducts(small) + " продукта");
Category deep = chain(100_000);
Thread worker = new Thread(null, () -> {
    try {
        System.out.println("Дълбочина 100000: " + countProducts(deep) + " продукта");
    } catch (StackOverflowError e) {
        System.out.println("Дълбочина 100000: " + e);
    }
}, "catalog", 1024 * 1024);
worker.start();
worker.join();

Изход

Дълбочина 900: 900 продукта
Дълбочина 100000: java.lang.StackOverflowError

StackOverflowError е Error, не Exception. Тук обходът върви в нишка със стек от 1 MB (четвъртият аргумент на new Thread), за да е еднакво на всяка машина. 900 нива минават, 100 000 не.

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

Виж го

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

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

public void withdraw(int amount) {
    if (amount > balance) {
        throw new IllegalArgumentException("Не стигат парите");
    }
    balance -= amount;
}
static void payRent(Account account) {
    account.withdraw(800);
    System.out.println("Наемът е платен.");
}

try {
    payRent(new Account(500));
} catch (IllegalArgumentException e) {
    System.out.println("Отказано: " + e.getMessage());
}

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

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

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

Идеята

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

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

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

kitchen.add(home);
try {
    System.out.println("Продукти: " + countProducts(shop));
} catch (StackOverflowError e) {
    System.out.println("С кръг: " + e);
}

Изход

С кръг: java.lang.StackOverflowError

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

Идеята

Две дъна

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

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

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("Кухня", "Градина")) {
    Category found = find(shop, name);
    if (found == null) {
        System.out.println(name + ": няма такава категория");
    } else {
        System.out.println(name + ": " + found.products + " продукта");
    }
}

Изход

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

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

Пробвай

Попълни

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

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 ;
}

Провери

Пробвай

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

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

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

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

Провери

Упражнение

Пътечката

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

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

Вход

Кухня

Изход

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

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

Още задачи

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

По-точно

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

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

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

Размерът. В Java всяка нишка има свой стек. Размерът по подразбиране се сменя с -Xss: 1 MB на x64, 2 MB на 64-битов ARM под Linux, а нова нишка може да получи свой, като четвърти аргумент на new Thread, както в програмата горе. Проверката на сайта пуска програмите с -Xss8m, затова обходът тук е в нишка от 1 MB.

Големината на рамката. Колко рамки се събират, зависи от рамката: повече параметри и локални променливи са повече байтове. 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: острови и кръгове
• Задачи по темата: Рекурсия