От рекурсия към цикъл

Код на:JavaC#PythonJavaScript

Накратко: Рекурсията може да стане цикъл: опашковото извикване става while, а обходът на дърво става цикъл със свой стек, който не свършва при дълбоки данни.

Проблем

Дървото идва отвън

В урока „Стекът от извиквания отвътре“ обходът на каталога падна на две места: веригата от импорта беше дълбока 100 000 нива, а друг импорт затвори кръг. Голям стек не е решение. sys.setrecursionlimit само мести границата: следващият импорт може да е по-дълбок, а истинският стек на процеса свършва без съобщение.

Дървото идва отвън: от доставчик, от API, от база. Не можеш да обещаеш колко е дълбоко. Трябва ти обход, чиято памет не зависи от стека от извиквания.

Идеята

Опашкова рекурсия

Започни от по-проста задача. Над продукта магазинът показва на кое ниво е категорията му. Нивото се брои нагоре по родителите, докато стигнеш корена:

def level_of(category, level):
    if category.parent is None:
        return level
    return level_of(category.parent, level + 1)

Тук рекурсивното извикване е последното, което функцията прави: резултатът му се връща направо, без + 1 и без цикъл след него. Такова извикване се казва опашково (tail call), а рекурсията е опашкова. След него рамката няма какво повече да помни. Език, който го знае, може да я ползва наново, вместо да слага нова: стекът не расте.

Само че:

• Java не го прави. JVM пази всяка рамка.
• C# компилаторът не го прави. JIT компилаторът понякога го прави в оптимизиран код, но не е обещано: при нашата проба с .NET 10 в Release стекът пак се препълни.
• Python не го прави нарочно: Гуидо ван Росум е против, защото traceback-ът ще губи рамки.
• JavaScript по стандарта (ES2015, в strict mode) трябва да го прави. На практика го прави само Safari. V8 (Chrome, Node) и Firefox не го правят.

Затова и опашковата рекурсия пада на веригата от импорта:

last = chain(100_000)
while last.children:
    last = last.children[0]
try:
    print("Рекурсия: ниво " + str(level_of(last, 0)))
except RecursionError as e:
    print(f"Рекурсия: RecursionError: {e}")
print("Цикъл: ниво " + str(level_of_loop(last)))

Изход

Рекурсия: RecursionError: maximum recursion depth exceeded
Цикъл: ниво 99999

Идеята

Опашковото извикване става while

Опашковата рекурсия се превръща в цикъл механично, по три правила:

• параметрите стават променливи: category и level;
• извикването става присвояване: вместо да викаш себе си с новите стойности, ги слагаш в променливите и почваш отначало;
• дъното става условието за край на цикъла: „родител няма“ спира while.

def level_of_loop(category):
    level = 0
    while category.parent is not None:
        category = category.parent
        level += 1
    return level

Това е долният ред в изхода отгоре: цикълът стига до ниво 99 999 с една рамка. Рекурсията и цикълът правят еднакъв брой стъпки, по една на ниво. Разликата е само къде стои паметта.

Идеята

Обходът не е опашков

count_products от предишния урок не е опашкова. След всяко извикване има работа: total += и следващото дете от цикъла. Затова рамките трябват. Какво пазеха те всъщност? Категориите, до които още не е стигнал.

Цикълът може да пази това сам, в свой стек: списък с категориите, които предстоят. Взимаш най-горната, прибавяш продуктите ѝ и слагаш децата ѝ отгоре. Сумата е една променлива, защото събирането не зависи от реда.

def count_products(root):
    total = 0
    stack = [root]
    while stack:
        category = stack.pop()
        total += category.products
        stack.extend(category.children)
    return total


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

Изход

Продукти: 20

Списъкът е стек: append и extend слагат накрая, pop() взима от края. Как работят отвътре, е в урока „Стек и опашка“.

Виж го

Свой стек, стъпка по стъпка

def count_products(root):
    total = 0
    stack = [root]
    while stack:
        category = stack.pop()
        total += category.products
        stack.extend(category.children)
    return total

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

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

1. Стекът е списък в паметта за обекти (heap), а не стекът от извиквания. Първо влиза коренът.
2. pop взима най-горния: Магазин. Децата му влизат отгоре: Електроника, после Дом.
3. Следва Дом, а не Електроника: стекът връща последното сложено. total = 4, влиза Кухня.
4. Кухня няма деца: нищо не влиза. total = 10.
5. Чак сега Електроника: total = 12. Влизат Телефони и Лаптопи.
6. Лаптопи (15), после Телефони (20).
7. Стекът е празен: цикълът спира и връща 20. В него никога не е имало повече от 2 категории. Редът обаче е Магазин, Дом, Кухня, Електроника, Лаптопи, Телефони: не като при рекурсията.

Своят стек е обикновен обект в паметта за обекти (heap). Той расте колкото трябва и е ограничен от цялата памет, не от 1 MB. А номерата в дървото показват, че редът е друг.

Пробвай

Предвиди реда

Същият обход, но печата името на всяка категория, щом я извади от стека:

def print_order(root):
    stack = [root]
    while stack:
        category = stack.pop()
        print(category.name)
        stack.extend(category.children)


print_order(shop)

Отговор

Магазин
Електроника
Дом
Телефони
Лаптопи
Кухня

Магазин
Дом
Кухня
Електроника
Лаптопи
Телефони

Магазин
Електроника
Телефони
Лаптопи
Дом
Кухня

Провери

Идеята

Редът на рекурсията: децата наобратно

За сумата редът няма значение. За менюто има: „Дом“ не бива да излиза преди „Електроника“. Рекурсията минава първо родителя, после децата отляво надясно (pre-order). Със свой стек същият ред излиза, когато слагаш децата наобратно: последното дете влиза първо и излиза последно.

Менюто трябва и отстъп. При рекурсия нивото щеше да е параметър, тоест в рамката. Сега рамка няма, затова стекът пази двойки: категорията и нивото ѝ. Каквото пазеше рамката, сега го пази твоят стек.

def print_menu(root):
    stack = [(root, 0)]
    while stack:
        category, level = stack.pop()
        print("  " * level + category.name)
        for child in reversed(category.children):
            stack.append((child, level + 1))


print_menu(shop)

Изход

Магазин
  Електроника
    Телефони
    Лаптопи
  Дом
    Кухня

В стека стоят кортежи (category, level). reversed() чете списъка отзад напред, без да го копира.

Виж го

Дълбокото дърво минава

Веригата от импорта, 100 000 нива, с обхода от урока:

deep = chain(100_000)
print(f"Дълбочина 100000: {count_products(deep)} продукта")

Изход

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

На четирите езика, без нишка с голям стек и без да пипаш граници.

Тук няма Bench, нарочно. Рекурсията и цикълът правят еднакъв брой операции: по една на категория, O(n). Кривите щяха да съвпаднат. Разликата е в паметта: рекурсията държи до дълбочината рамки в малкия стек, цикълът държи чакащите категории в heap-а. При широко дърво своят стек може да е голям (всички чакащи братя и сестри), но мястото за него е цялата памет.

Идеята

Кръгът иска памет за видяното

Своят стек не спасява от кръга. Ако „Дом“ е в „Кухня“, а „Кухня“ в „Дом“, двете се редуват в стека вечно. Стекът дори не расте, затова нищо не се препълва и нищо не се хвърля: страницата просто виси. Това е по-лошо от грешката.

Поправката е множество от видените категории. Преди да обходиш категория, провери дали вече я има в него:

def count_products(root):
    total = 0
    seen = set()
    stack = [root]
    while stack:
        category = stack.pop()
        if category in seen:
            print("Пропускам " + category.name + ": вече е обходена")
            continue
        seen.add(category)
        total += category.products
        stack.extend(category.children)
    return total


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

Изход

Пропускам Дом: вече е обходена
Продукти: 20

Обект без __eq__ и __hash__ се сравнява по самоличност: set пази самите категории, не имената им. Същото множество спасява и рекурсията: count_products с параметър „видени“ спира кръга. Срещу дълбочината обаче помага само цикълът.

Пробвай

Подреди редовете

Подреди обхода със свой стек:

1. category = stack.pop()↑↓
2. while stack:↑↓
3. return total↑↓
4. def count_products(root):↑↓
5. stack = [root]↑↓
6. total = 0↑↓
7. total += category.products↑↓
8. stack.extend(category.children)↑↓

Провери

Пробвай

Попълни

Кога спира цикълът?

def count_products(root):
    total = 0
    stack = [root]
    while :
        category = stack.pop()
        total += category.products
        stack.extend(category.children)
    return total

Провери

Упражнение

Най-дълбокото ниво

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

Колко дълбок е каталогът. Импортът слага веригата си под „Кухня“. Прочети колко нива е веригата, закачи я и отпечатай колко категории има общо и кое е най-дълбокото ниво (Магазин е на ниво 0). Без рекурсия: стек с двойки категория и ниво, като в менюто.

Вход

100000

Изход

Категории: 100006
Най-дълбоко ниво: 100002

Още задачи

• Пътечката без рекурсия. Пренапиши path от предишния урок с цикъл нагоре по родителите. Списъкът се пълни отзад напред.
• Менюто с броя продукти. Отпечатай менюто, но до всяка категория сумата заедно с подкатегориите. Подсказка: сумата на родителя е готова чак след децата, затова при цикъл всяка категория влиза в стека два пъти: веднъж „отвори“ и веднъж „сумирай“.

По-точно

Стекът във всеки език

Стекът се пише по различен начин във всеки език, а и не всеки стек е добър избор.

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

• Python: списъкът е бърз стек (append и pop() от края са O(1)). За опашка се ползва collections.deque: pop(0) от списък е O(n).
• Генератор с yield from прави рекурсивния обход кратък, но под него пак има рамки: дълбочината пак удря границата от 1000.

Trampoline. Функцията не вика себе си, а връща „какво да се извика после“, а цикъл отвън го вика. Така опашковата рекурсия върви без растящ стек и в езици без опашкови извиквания. Работи, но цикълът, написан направо, е по-ясен.

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

Тест

Провери се

1. Кое от тези извиквания е опашково?

total += count_products(child);return 1 + months(debt - payment, payment);return level_of(category.parent, level + 1);

2. Кой от четирите езика превръща опашковата рекурсия в цикъл, така че стекът да не расте?

Всички, когато извикването е последноНито един на практика: Java, C# и Python не го правят, а стандартът на JavaScript го иска, но V8 (Node, Chrome) не го правиСамо Python

3. Защо обходът със свой стек минава веригата от 100 000 нива, а рекурсията не?

Своят стек е обект в паметта за обекти и расте колкото трябва, а рамката на функцията е еднаСвоят стек пази само по една категорияЦикълът прави по-малко операции

4. Децата на категорията влизат в своя стек в реда им: Телефони, после Лаптопи. Коя излиза първа?

Лаптопи: стекът връща последното сложеноЗависи от езикаТелефони: тя е първа

5. Какво става, ако обходът със свой стек срещне кръг (Дом → Кухня → Дом) и не помни видените категории?

Върти се безкрайно, без грешка: Дом и Кухня се редуват в стекаВръща грешна сума и спираХвърля StackOverflowError

Провери

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

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

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