Рекурсия, стек, очередь

Рекурсия, стек, очередь

Технический фундамент порядка обработки

Эти три темы описывают не только структуры, но и стратегию выполнения:

  • рекурсия естественно выражает вложенную структуру;
  • стек задает обратный порядок (LIFO);
  • очередь задает порядок поступления (FIFO).

Выбор стратегии определяет и поведение, и ограничения по памяти/глубине вызова.

Почему эти структуры и подходы важны

Рекурсия, стек и очередь это базовые инструменты для управления порядком обработки данных. Они встречаются в парсинге, обходе структур, планировщиках задач, истории навигации, обработке событий.

Ключевой момент: выбор между рекурсией, стеком и очередью определяет порядок выполнения и потребление памяти.

Проверь себя: почему для "обработать сначала самое старое" лучше очередь, а не стек?

Рекурсия: функция вызывает саму себя

Рекурсия полезна, когда задача естественно разбивается на "меньшую такую же задачу".

function factorial(n) {
  if (n <= 1) return 1; // базовый случай
  return n * factorial(n - 1);
}

console.log(factorial(5)); // 120

Два обязательных элемента:

  • базовый случай (когда остановиться);
  • рекурсивный шаг (как приблизиться к базовому).

Здесь часто путаются: без базового случая будет бесконечный вызов и переполнение стека.

Смотри, что важно: рекурсия использует call stack движка. При слишком глубокой рекурсии ты получишь RangeError: Maximum call stack size exceeded. В JavaScript нельзя рассчитывать на оптимизацию хвостовой рекурсии, поэтому для больших структур часто безопаснее цикл + явный стек/очередь.

Стек (LIFO)

Стек работает по принципу "последним пришел - первым вышел" (Last In, First Out).

const stack = [];
stack.push('A');
stack.push('B');

console.log(stack.pop()); // B
console.log(stack.pop()); // A

Мини-сценарий: история действий "undo", где откатывается последнее изменение.

Дополнительный пример: проверка сбалансированности скобок через стек.

function isBalanced(str) {
  const stack = [];
  const pairs = { ')': '(', ']': '[', '}': '{' };

  for (const ch of str) {
    if (ch === '(' || ch === '[' || ch === '{') stack.push(ch);
    else if (ch === ')' || ch === ']' || ch === '}') {
      if (stack.pop() !== pairs[ch]) return false;
    }
  }

  return stack.length === 0;
}

Очередь (FIFO)

Очередь работает как "первым пришел - первым вышел" (First In, First Out).

const queue = [];
queue.push('task-1');
queue.push('task-2');

console.log(queue.shift()); // task-1
console.log(queue.shift()); // task-2

Мини-сценарий: обработка запросов в порядке поступления.

Смотри, что важно: у массива shift() может быть дороже на больших данных, поэтому в прод-системах очередь часто делают на специализированной структуре.

Рекурсия vs явный стек

Некоторые рекурсивные задачи можно переписать через явный стек.

function countDown(n) {
  const stack = [n];
  while (stack.length) {
    const current = stack.pop();
    if (current < 0) continue;
    console.log(current);
    stack.push(current - 1);
  }
}

Дополнительный пример: обход дерева в ширину через очередь (BFS).

function bfs(root) {
  const queue = [root];
  while (queue.length) {
    const node = queue.shift();
    console.log(node.value);
    for (const child of node.children ?? []) queue.push(child);
  }
}

Это помогает контролировать процесс и снижать риск глубокого рекурсивного вызова.

Проверь себя: когда рекурсия читается проще, а когда безопаснее использовать цикл + стек?

Реальные микро-сценарии

  1. Обход вложенных комментариев (рекурсия).
  2. История браузерных переходов назад (стек).
  3. Очередь задач отправки уведомлений (FIFO).

Эти паттерны кажутся базовыми, но на них строится много продакшен-механик.

Частые ошибки новичков

  • Забывать базовый случай в рекурсии.
  • Путать порядок LIFO и FIFO.
  • Использовать рекурсию для очень глубоких структур без учета лимита стека.
  • Выбирать "по привычке", а не по требованиям порядка обработки.

Анти-провал: перед реализацией всегда проговори правило порядка: "последний первый" или "первый первый".

Что будет, если изменить входные данные

Для рекурсии факториала при n = 0 базовый случай должен вернуть 1, иначе логика сломается. Для очереди, если добавлять задачи быстрее, чем обрабатываешь, очередь растет и нужна стратегия ограничения/батчинга.

Проверь себя: что будет с рекурсией на очень большом n без оптимизаций?

Краткий итог

  • Рекурсия удобна для задач с естественной самоподобной структурой.
  • Стек (LIFO) и очередь (FIFO) задают разные модели порядка обработки.
  • Правильный выбор структуры зависит от бизнес-правила последовательности.
  • Рекурсия требует базового случая и контроля глубины.
  • Эти паттерны лежат в основе множества реальных сценариев: от UI-истории до серверных очередей.