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

Код на:JavaC#PythonJavaScript

Накратко: Стекът от извиквания пази по една рамка за всяко незавършило извикване; при твърде дълбока рекурсия той свършва и идва RangeError: Maximum call stack size exceeded.

Проблем

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

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

function countProducts(category) {
  let total = category.products;
  for (const child of category.children) {
    total += countProducts(child);
  }
  return total;
}

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

Изход

Продукти: 20

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

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

Идеята

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

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

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

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

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

function factorial(n) {
  if (n === 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

console.log(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 и програмата го отпечатва.

Виж го

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

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

function countProducts(category) {
  let total = category.products;
  for (const child of category.children) {
    total += countProducts(child);
  }
  return total;
}

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

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

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

Пробвай

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

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

let depth = 0;
let deepest = 0;

function countProducts(category) {
  depth++;
  deepest = Math.max(deepest, depth);
  let total = category.products;
  for (const child of category.children) {
    total += countProducts(child);
  }
  depth--;
  return total;
}

const total = countProducts(shop);
console.log(`${total} продукта, най-много ${deepest} рамки наведнъж`);

Отговор

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

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

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

Провери

Идеята

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

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

console.log(`Дълбочина 900: ${countProducts(chain(900))} продукта`);
try {
  console.log(`Дълбочина 100000: ${countProducts(chain(100_000))} продукта`);
} catch (e) {
  console.log(`Дълбочина 100000: ${e.name}: ${e.message}`);
}

Изход

Дълбочина 900: 900 продукта
Дълбочина 100000: RangeError: Maximum call stack size exceeded

В Node стекът е около 1 MB. Колко извиквания събира, зависи от рамката: за countProducts са около 10 000. 900 нива минават, 100 000 не.

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

Виж го

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

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

withdraw(amount) {
  if (amount > this.balance) {
    throw new RangeError("Не стигат парите");
  }
  this.balance -= amount;
}

function payRent(account) {
  account.withdraw(800);
  console.log("Наемът е платен.");
}

try {
  payRent(new Account(500));
} catch (e) {
  console.log(`Отказано: ${e.message}`);
}

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

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

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

Идеята

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

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

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

kitchen.add(home);
try {
  console.log("Продукти: " + countProducts(shop));
} catch (e) {
  console.log(`С кръг: ${e.name}: ${e.message}`);
}

Изход

С кръг: RangeError: Maximum call stack size exceeded

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

Идеята

Две дъна

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

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

function find(category, name) {
  if (category.name === name) {
    return category;
  }
  for (const child of category.children) {
    const found = find(child, name);
    if (found !== null) {
      return found;
    }
  }
  return null;
}

for (const name of ["Кухня", "Градина"]) {
  const found = find(shop, name);
  if (found === null) {
    console.log(name + ": няма такава категория");
  } else {
    console.log(`${name}: ${found.products} продукта`);
  }
}

Изход

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

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

Пробвай

Попълни

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

function find(category, name) {
  if (category.name === name) {
    return category;
  }
  for (const child of category.children) {
    const found = find(child, name);
    if (found !== null) {
      return found;
    }
  }
  return ;
}

Провери

Пробвай

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

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

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

1function months(debt, payment) {2 if (debt === 0) {3 return 0;4 }5 return 1 + months(debt - payment, payment);6}

Провери

Упражнение

Пътечката

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

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

Вход

Кухня

Изход

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

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

Още задачи

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

По-точно

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

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

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

Размерът. В Node стекът е около 1 MB и се сменя с node --stack-size=…. По-голяма стойност от тази, която операционната система дава на процеса, не помага: процесът пада без RangeError. В браузъра размерът е друг за всеки браузър.

Големината на рамката. Колко рамки се събират, зависи от рамката: повече параметри и локални променливи са повече байтове. Затова в 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), а другите мерят байтове памет, затова броят извиквания зависи от големината на рамката

Провери

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

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

• Нужно отпреди: Стрелкови функции · Async, await и нишки · Big-O: как расте работата · Сложност по памет
• Продължава в: От рекурсия към цикъл · Бързо степенуване · Двоично дърво за търсене · DFS: острови и кръгове
• Задачи по темата: Рекурсия