Стек вызовов

Что такое стек вызовов?

Стек вызовов — это структура данных (стек — LIFO), которая отслеживает активные вызовы функций. Каждый раз, когда функция вызывается, создаётся новый stack frame и заталкивается в стек. Frame содержит:

1. Параметры функции.
2. Её локальные переменные.
3. Адрес возврата (где в вызывающем коде продолжить после возврата этой функции).

Когда функция возвращается, её frame выталкивается из стека, и управление переходит вызывающему коду.

Как стек растёт и сжимается

Рассмотри простой пример:

function foo() { bar(); }
function bar() { baz(); }
function baz() { return 42; }

foo();

Когда ты вызываешь foo():

1. Frame для foo() заталкивается.
2. foo() вызывает bar(), заталкивается frame для bar().
3. bar() вызывает baz(), заталкивается frame для baz().
4. baz() возвращает 42 → её frame выталкивается.
5. bar() возвращается → её frame выталкивается.
6. foo() возвращается → её frame выталкивается.

На шаге 3 стек содержит [foo, bar, baz] (baz на вершине, следующий к запуску). Глубина стека = 3.

Рекурсия и стек вызовов

Рекурсия — просто частный случай: функция вызывает саму себя. Каждый рекурсивный вызов заталкивает новый frame.

Давай проследим factorial(4):

1. Вызови factorial(4) → заталкни frame [n=4].
2. Вызови factorial(3) → заталкни frame [n=3]. Стек: [factorial(4), factorial(3)].
3. Вызови factorial(2) → заталкни frame [n=2]. Стек: [factorial(4), factorial(3), factorial(2)].
4. Вызови factorial(1) → заталкни frame [n=1]. Стек: [factorial(4), factorial(3), factorial(2), factorial(1)].
5. factorial(1) попадает в базовый случай, возвращает 1 → выталкни [n=1]. Стек: [factorial(4), factorial(3), factorial(2)].
6. factorial(2) получает ответ 1, вычисляет 2 × 1 = 2, возвращается → выталкни [n=2]. Стек: [factorial(4), factorial(3)].
7. factorial(3) получает ответ 2, вычисляет 3 × 2 = 6, возвращается → выталкни [n=3]. Стек: [factorial(4)].
8. factorial(4) получает ответ 6, вычисляет 4 × 6 = 24, возвращается → выталкни [n=4]. Стек пуст.

На шаге 4 (самая глубокая точка) глубина стека = 4. Это n — размер входа.

Стек имеет конечный размер

Память твоего компьютера ограничена. Стек (область памяти, где живут frames) имеет фиксированный размер — обычно несколько мегабайт. Если рекурсия заходит слишком глубоко и продолжает заталкивать frames без выталкивания, она может исчерпать это место.

Когда стек исчерпывает свою память, происходит переполнение стека: программа падает с ошибкой вроде “Maximum call stack size exceeded.” Это жёсткий предел, который нельзя игнорировать.

function badLoop(n) {
  return badLoop(n + 1); // Нет базового случая! Бесконечная рекурсия.
}

badLoop(0); // В итоге: переполнение стека.

Даже с базовым случаем, если рекурсия достаточно глубока, ты упрёшься в лимит:

function deepRecursion(n) {
  if (n === 0) return 1;
  return deepRecursion(n - 1); // Каждый вызов заталкивает frame.
}

deepRecursion(1000000); // На большинстве систем: переполнение стека.

Память стека — это пространственная сложность

На прошлом уроке ты видел, что factorial(n) имеет O(n) пространственную сложность. Теперь ты понимаешь почему: каждый рекурсивный вызов заталкивает frame. Самая глубокая рекурсия достигает глубины n, поэтому стек содержит одновременно до n frames. То есть O(n) памяти стека.

Если ты вызовешь factorial(1000), 1000 frames накапливаются до того, как самый глубокий вызов начнёт возвращаться. Если вызовешь factorial(1000000), стек переполнится задолго до завершения.

Рекурсия можно переписать итеративно

Любую рекурсию можно, в принципе, переписать с явным циклом и явным стеком (или другой структурой). Рекурсия — удобство: стек вызовов ведёт учёт за тебя. Но если память стека — проблема, ты можешь обменять рекурсию на итерацию + ручное управление стеком.

Пример: вычисли факториал итеративно (без рекурсии).

function factorialIterative(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

Это использует O(1) памяти — нет рекурсивных вызовов, только один цикл. Но это менее интуитивно, когда задача естественно рекурсивна (вроде обхода дерева).