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

Код на:JavaC#PythonJavaScript

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

Проблем

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

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

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

Идеята

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

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

static int levelOf(Category category, int level) {
    if (category.parent == null) {
        return level;
    }
    return levelOf(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 не го правят.

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

Category last = chain(100_000);
while (!last.children.isEmpty()) {
    last = last.children.get(0);
}
Category deepest = last;
Thread worker = new Thread(null, () -> {
    try {
        System.out.println("Рекурсия: ниво " + levelOf(deepest, 0));
    } catch (StackOverflowError e) {
        System.out.println("Рекурсия: " + e);
    }
}, "catalog", 1024 * 1024);
worker.start();
worker.join();
System.out.println("Цикъл: ниво " + levelOfLoop(deepest));

Изход

Рекурсия: java.lang.StackOverflowError
Цикъл: ниво 99999

Рекурсията върви в нишка със стек от 1 MB, за да е еднакво на всяка машина.

Идеята

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

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

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

static int levelOfLoop(Category category) {
    int level = 0;
    while (category.parent != null) {
        category = category.parent;
        level++;
    }
    return level;
}

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

Идеята

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

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

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

static int countProducts(Category root) {
    int total = 0;
    Deque<Category> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Category category = stack.pop();
        total += category.products;
        for (Category child : category.children) {
            stack.push(child);
        }
    }
    return total;
}

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

Изход

Продукти: 20

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

Виж го

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

static int countProducts(Category root) {
    int total = 0;
    Deque<Category> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Category category = stack.pop();
        total += category.products;
        for (Category child : category.children) {
            stack.push(child);
        }
    }
    return total;
}

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

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

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

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

Пробвай

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

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

static void printOrder(Category root) {
    Deque<Category> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Category category = stack.pop();
        System.out.println(category.name);
        for (Category child : category.children) {
            stack.push(child);
        }
    }
}

printOrder(shop);

Отговор

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

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

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

Провери

Идеята

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

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

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

static void printMenu(Category root) {
    Deque<Entry> stack = new ArrayDeque<>();
    stack.push(new Entry(root, 0));
    while (!stack.isEmpty()) {
        Entry entry = stack.pop();
        Category category = entry.category();
        System.out.println("  ".repeat(entry.level()) + category.name);
        for (Category child : category.children.reversed()) {
            stack.push(new Entry(child, entry.level() + 1));
        }
    }
}

printMenu(shop);

Изход

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

Entry е запис с двете полета: record Entry(Category category, int level) {}. children.reversed() (от Java 21) е изглед, който чете списъка отзад напред, без да го копира.

Виж го

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

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

Category deep = chain(100_000);
System.out.println("Дълбочина 100000: " + countProducts(deep) + " продукта");

Изход

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

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

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

Идеята

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

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

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

static int countProducts(Category root) {
    int total = 0;
    Set<Category> seen = new HashSet<>();
    Deque<Category> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Category category = stack.pop();
        if (!seen.add(category)) {
            System.out.println("Пропускам " + category.name + ": вече е обходена");
            continue;
        }
        total += category.products;
        for (Category child : category.children) {
            stack.push(child);
        }
    }
    return total;
}

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

Изход

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

seen.add връща false, ако категорията вече е вътре: една проверка вместо две. Category не презаписва equals и hashCode, затова HashSet сравнява самите обекти, а не имената. Същото множество спасява и рекурсията: countProducts с параметър „видени“ спира кръга. Срещу дълбочината обаче помага само цикълът.

Пробвай

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

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

1. Deque<Category> stack = new ArrayDeque<>();↑↓
2. }↑↓
3. return total;↑↓
4. for (Category child : category.children) {↑↓
5. Category category = stack.pop();↑↓
6. }↑↓
7. stack.push(child);↑↓
8. while (!stack.isEmpty()) {↑↓
9. int total = 0;↑↓
10. static int countProducts(Category root) {↑↓
11. }↑↓
12. stack.push(root);↑↓
13. total += category.products;↑↓

Провери

Пробвай

Попълни

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

static int countProducts(Category root) {
    int total = 0;
    Deque<Category> stack = new ArrayDeque<>();
    stack.push(root);
    while () {
        Category category = stack.pop();
        total += category.products;
        for (Category child : category.children) {
            stack.push(child);
        }
    }
    return total;
}

Провери

Упражнение

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

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

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

Вход

100000

Изход

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

Още задачи

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

По-точно

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

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

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

• Java: ArrayDeque е препоръчаният стек. Старият клас Stack наследява Vector: синхронизира всяка операция, затова е по-бавен, а get(i) дава достъп и до средата на стека.
• Рекурсия в нишка с голям стек (new Thread(null, work, name, 64 * 1024 * 1024)) е честа временна мярка. Цикълът е поправката.

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

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

Тест

Провери се

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

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

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

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

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

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

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

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

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

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

Провери

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

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

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