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

Код на: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 не го правят.

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

var last = Chain(100_000);
while (last.Children.Count > 0)
{
    last = last.Children[0];
}
var worker = new Thread(() =>
{
    try
    {
        Console.WriteLine("Рекурсия: ниво " + LevelOf(last, 0));
    }
    catch (InsufficientExecutionStackException e)
    {
        Console.WriteLine("Рекурсия: " + e.GetType().Name);
    }
}, 1024 * 1024);
worker.Start();
worker.Join();
Console.WriteLine("Цикъл: ниво " + LevelOfLoop(last));

Изход

Рекурсия: InsufficientExecutionStackException
Цикъл: ниво 99999

Рекурсията върви в нишка със стек от 1 MB, а LevelOf има предпазителя от предишния урок, RuntimeHelpers.EnsureSufficientExecutionStack(): истинското препълване щеше да убие процеса.

Идеята

Опашковото извикване става 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;
    var stack = new Stack<Category>();
    stack.Push(root);
    while (stack.Count > 0)
    {
        Category category = stack.Pop();
        total += category.Products;
        foreach (Category child in category.Children)
        {
            stack.Push(child);
        }
    }
    return total;
}

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

Изход

Продукти: 20

Stack<T>: Push слага отгоре, Pop взима отгоре. Как работят отвътре, е в урока „Стек и опашка“.

Виж го

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

static int CountProducts(Category root)
{
    int total = 0;
    var stack = new Stack<Category>();
    stack.Push(root);
    while (stack.Count > 0)
    {
        Category category = stack.Pop();
        total += category.Products;
        foreach (Category child in category.Children)
        {
            stack.Push(child);
        }
    }
    return total;
}

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

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

1. Стекът е Stack<Category> в паметта за обекти (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)
{
    var stack = new Stack<Category>();
    stack.Push(root);
    while (stack.Count > 0)
    {
        Category category = stack.Pop();
        Console.WriteLine(category.Name);
        foreach (Category child in category.Children)
        {
            stack.Push(child);
        }
    }
}

PrintOrder(shop);

Отговор

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

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

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

Провери

Идеята

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

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

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

static void PrintMenu(Category root)
{
    var stack = new Stack<(Category Category, int Level)>();
    stack.Push((root, 0));
    while (stack.Count > 0)
    {
        var (category, level) = stack.Pop();
        Console.WriteLine(new string(' ', 2 * level) + category.Name);
        for (int i = category.Children.Count - 1; i >= 0; i--)
        {
            stack.Push((category.Children[i], level + 1));
        }
    }
}

PrintMenu(shop);

Изход

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

В стека стоят кортежи (Category, int). Цикълът for върви отзад напред. Внимавай с category.Children.Reverse(): на List<T> това е методът, който обръща самия списък на място и не връща нищо, а менюто щеше да се обърне за постоянно.

Виж го

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

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

var deep = Chain(100_000);
Console.WriteLine($"Дълбочина 100000: {CountProducts(deep)} продукта");

Изход

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

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

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

Идеята

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

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

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

static int CountProducts(Category root)
{
    int total = 0;
    var seen = new HashSet<Category>();
    var stack = new Stack<Category>();
    stack.Push(root);
    while (stack.Count > 0)
    {
        Category category = stack.Pop();
        if (!seen.Add(category))
        {
            Console.WriteLine("Пропускам " + category.Name + ": вече е обходена");
            continue;
        }
        total += category.Products;
        foreach (Category child in category.Children)
        {
            stack.Push(child);
        }
    }
    return total;
}

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

Изход

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

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

Пробвай

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

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

1. {↑↓
2. foreach (Category child in category.Children)↑↓
3. }↑↓
4. {↑↓
5. static int CountProducts(Category root)↑↓
6. stack.Push(child);↑↓
7. var stack = new Stack<Category>();↑↓
8. int total = 0;↑↓
9. return total;↑↓
10. }↑↓
11. }↑↓
12. Category category = stack.Pop();↑↓
13. while (stack.Count > 0)↑↓
14. stack.Push(root);↑↓
15. total += category.Products;↑↓
16. {↑↓

Провери

Пробвай

Попълни

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

static int CountProducts(Category root)
{
    int total = 0;
    var stack = new Stack<Category>();
    stack.Push(root);
    while ()
    {
        Category category = stack.Pop();
        total += category.Products;
        foreach (Category child in category.Children)
        {
            stack.Push(child);
        }
    }
    return total;
}

Провери

Упражнение

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

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

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

Вход

100000

Изход

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

Още задачи

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

По-точно

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

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

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

• C#: Stack<T> е масив отвътре, който се удвоява, когато се напълни. Queue<T> е същото за опашка.
• new Thread(work, 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: острови и кръгове · Припокриващи се подзадачи
• Задачи по темата: Рекурсия