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

Код на:JavaC#PythonJavaScript

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

Проблем

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

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

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


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

Изход

Продукти: 20

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

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

Идеята

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

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

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

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

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

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


print(factorial(3))  # 6

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

1. Програмата вика 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 и програмата го отпечатва.

Виж го

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

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

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

print("Продукти: " + str(count_products(shop)))

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

1. Програмата вика count_products(shop). Засега в стека е само рамката на програмата.
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.

Пробвай

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

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

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} продукта, най-много {deepest} рамки наведнъж")

Отговор

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

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

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

Провери

Идеята

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

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

print("Границата на Python:", sys.getrecursionlimit())
print(f"Дълбочина 900: {count_products(chain(900))} продукта")
try:
    print(f"Дълбочина 100000: {count_products(chain(100_000))} продукта")
except RecursionError as e:
    print(f"Дълбочина 100000: RecursionError: {e}")

Изход

Границата на Python: 1000
Дълбочина 900: 900 продукта
Дълбочина 100000: RecursionError: maximum recursion depth exceeded

Python спира още при 1000 рамки, много преди истинският стек да свърши. Това е предпазител, а не дъното на паметта: 900 нива минават, 1000 вече не.

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

Виж го

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

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

def withdraw(self, amount):
    if amount > self.balance:
        raise ValueError("Не стигат парите")
    self.balance -= amount


def pay_rent(account):
    account.withdraw(800)
    print("Наемът е платен.")


try:
    pay_rent(Account(500))
except ValueError as e:
    print(f"Отказано: {e}")

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

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

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

Идеята

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

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

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

kitchen.add(home)
try:
    print("Продукти: " + str(count_products(shop)))
except RecursionError as e:
    print(f"С кръг: RecursionError: {e}")

Изход

С кръг: RecursionError: maximum recursion depth exceeded

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

Идеята

Две дъна

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

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

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 ["Кухня", "Градина"]:
    found = find(shop, name)
    if found is None:
        print(name + ": няма такава категория")
    else:
        print(f"{name}: {found.products} продукта")

Изход

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

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

Пробвай

Попълни

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

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 

Провери

Пробвай

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

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

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

1def months(debt, payment):2 if debt == 0:3 return 04 return 1 + months(debt - payment, payment)

Провери

Упражнение

Пътечката

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

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

Вход

Кухня

Изход

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

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

Още задачи

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

По-точно

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

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

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

Размерът. В Python границата е брой рамки: sys.getrecursionlimit() е 1000. sys.setrecursionlimit(100_000) вдига границата, но не и истинския стек на процеса: при достатъчно дълбока рекурсия Python пада без съобщение. За да имаш наистина повече място, трябва нишка с по-голям стек (threading.stack_size), а и тогава веригата от импорта може да е по-дълбока от него.

Големината на рамката. Колко рамки се събират, зависи от рамката: повече параметри и локални променливи са повече байтове. Затова в Node броят извиквания до препълването не е точно число, а в Python е, защото там се броят рамките.

Дървото и паметта на обектите. Самите категории не са в стека. Те са обекти в паметта за обекти (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: острови и кръгове
• Задачи по темата: Рекурсия