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

Код на:JavaC#PythonJavaScript

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

Проблем

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

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

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

Идеята

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

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

function levelOf(category, 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 не го правят.

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

let last = chain(100_000);
while (last.children.length > 0) {
  last = last.children[0];
}
try {
  console.log("Рекурсия: ниво " + levelOf(last, 0));
} catch (e) {
  console.log(`Рекурсия: ${e.name}: ${e.message}`);
}
console.log("Цикъл: ниво " + levelOfLoop(last));

Изход

Рекурсия: RangeError: Maximum call stack size exceeded
Цикъл: ниво 99999

Идеята

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

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

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

function levelOfLoop(category) {
  let level = 0;
  while (category.parent !== null) {
    category = category.parent;
    level++;
  }
  return level;
}

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

Идеята

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

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

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

function countProducts(root) {
  let total = 0;
  const stack = [root];
  while (stack.length > 0) {
    const category = stack.pop();
    total += category.products;
    stack.push(...category.children);
  }
  return total;
}

console.log("Продукти: " + countProducts(shop));

Изход

Продукти: 20

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

Виж го

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

function countProducts(root) {
  let total = 0;
  const stack = [root];
  while (stack.length > 0) {
    const category = stack.pop();
    total += category.products;
    stack.push(...category.children);
  }
  return total;
}

console.log("Продукти: " + countProducts(shop));

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

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

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

Пробвай

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

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

function printOrder(root) {
  const stack = [root];
  while (stack.length > 0) {
    const category = stack.pop();
    console.log(category.name);
    stack.push(...category.children);
  }
}

printOrder(shop);

Отговор

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

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

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

Провери

Идеята

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

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

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

function printMenu(root) {
  const stack = [[root, 0]];
  while (stack.length > 0) {
    const [category, level] = stack.pop();
    console.log("  ".repeat(level) + category.name);
    for (const child of category.children.toReversed()) {
      stack.push([child, level + 1]);
    }
  }
}

printMenu(shop);

Изход

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

В стека стоят масиви [category, level]. toReversed() (от 2023 г., Node 20) прави обърнато копие и не пипа children. reverse() щеше да обърне самия списък.

Виж го

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

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

const deep = chain(100_000);
console.log(`Дълбочина 100000: ${countProducts(deep)} продукта`);

Изход

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

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

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

Идеята

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

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

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

function countProducts(root) {
  let total = 0;
  const seen = new Set();
  const stack = [root];
  while (stack.length > 0) {
    const category = stack.pop();
    if (seen.has(category)) {
      console.log("Пропускам " + category.name + ": вече е обходена");
      continue;
    }
    seen.add(category);
    total += category.products;
    stack.push(...category.children);
  }
  return total;
}

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

Изход

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

Set сравнява обектите по референция: две категории с едно име са различни. Същото множество спасява и рекурсията: countProducts с параметър „видени“ спира кръга. Срещу дълбочината обаче помага само цикълът.

Пробвай

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

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

1. let total = 0;↑↓
2. const category = stack.pop();↑↓
3. while (stack.length > 0) {↑↓
4. const stack = [root];↑↓
5. }↑↓
6. return total;↑↓
7. total += category.products;↑↓
8. }↑↓
9. stack.push(...category.children);↑↓
10. function countProducts(root) {↑↓

Провери

Пробвай

Попълни

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

function countProducts(root) {
  let total = 0;
  const stack = [root];
  while () {
    const category = stack.pop();
    total += category.products;
    stack.push(...category.children);
  }
  return total;
}

Провери

Упражнение

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

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

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

Вход

100000

Изход

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

Още задачи

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

По-точно

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

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

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

• JavaScript: масивът е стек (push и pop от края са O(1)). shift() от началото е O(n), затова масивът не е добра опашка за много елементи.
• stack.push(...children) разпъва децата като аргументи. При стотици хиляди деца на една категория това само по себе си препълва стека: тогава се ползва цикъл с push за всяко дете.

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: острови и кръгове · Припокриващи се подзадачи
• Задачи по темата: Рекурсия