Язык JavaScript - Рекурсия и стек

картинка взята с ya.ru

Зов бездны: Как рекурсия и стек работают в JavaScript (и почему бесконечная рекурсия - это плохо)

Есть одна история. Программист зашёл в лифт. Нажал кнопку своего этажа. Лифт не поехал. Программист нажал ещё раз. Потом ещё. Потом начал нажимать всё быстрее. Вдруг он понял: он написал рекурсию без базового случая.

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

Но с великой силой приходит великая ответственность. Рекурсия может переполнить стек, съесть всю память и заставить браузер зависнуть. Или может быть изящным решением, которое сделает код прозрачным как стекло.

Сегодня мы разберём, как работает рекурсия, что такое стек вызовов, как избежать переполнения и когда использовать рекурсию, а когда - итерацию.

Часть 1. Что такое рекурсия?

Рекурсия - это когда функция вызывает саму себя.

Два обязательных компонента рекурсии:

1. Базовый случай (base case) - условие остановки (когда n <= 0).
2. Рекурсивный случай (recursive case) - вызов функции с изменёнными аргументами.

Без базового случая рекурсия станет бесконечной. А бесконечная рекурсия — это быстрый способ убить программу.

Часть 2. Стек вызовов (Call Stack)

Чтобы понять рекурсию, нужно понять стек. Стек - это структура данных "последним пришёл - первым ушёл" (LIFO).

Когда функция вызывается, она попадает на вершину стека. Когда функция завершается, она снимается со стека.

Как это работает в рекурсии?

Часть 3. Классические примеры рекурсии

3.1 Факториал

Как это работает:

factorial(5) = 5 * factorial(4)
= 5 * (4 * factorial(3))
= 5 * (4 * (3 * factorial(2)))
= 5 * (4 * (3 * (2 * factorial(1))))
= 5 * (4 * (3 * (2 * 1)))
= 5 * (4 * (3 * 2))
= 5 * (4 * 6)
= 5 * 24
= 120

3.2 Числа Фибоначчи

Дерево вызовов для fibonacci(4):

Много повторяющихся вычислений! Это неэффективно.

3.3 Сумма элементов массива

3.4 Степень числа

Часть 4. Рекурсия и итерация: что лучше?

Любую рекурсию можно переписать в виде цикла. И наоборот.

Сравнение:

Когда использовать рекурсию:

• Древовидные структуры (DOM, файловая система, графы)
• Задачи, которые естественно делятся на подзадачи (QuickSort, MergeSort)
• Обход в глубину (DFS)
• Задачи, где глубина заранее ограничена и невелика

Когда использовать итерацию:

• Простые линейные задачи (сумма, факториал, Фибоначчи)
• Когда глубина рекурсии может быть большой
• Когда важна производительность и память

Часть 5. Глубокие рекурсии и переполнение стека

У стека есть предел. В JavaScript максимальная глубина рекурсии — около 10 000–50 000 вызовов (зависит от движка).

Что произошло? Каждый вызов занимает место в стеке. Стек переполнился.

Как обойти переполнение?

1. Использовать итерацию вместо рекурсии

2. Хвостовая рекурсия (tail call optimization — TCO)

Хвостовая рекурсия - это когда рекурсивный вызов является последней операцией в функции.

Важно: В JavaScript TCO поддерживается только в строгом режиме и не во всех движках (в V8 только в Safari, в Chrome - нет). Не полагайтесь на это.

3. Ручное управление стеком (превращение рекурсии в итерацию с массивом)

Часть 6. Рекурсивный обход структур

6.1 Обход DOM

6.2 Обход файловой системы (концептуально)

6.3 Обход графа (поиск в глубину)

Часть 7. Оптимизация рекурсии: мемоизация

Проблема рекурсивного Фибоначчи - экспоненциальное количество вызовов. Мемоизация кэширует результаты.

Сравнение производительности:

• fibonacci(40) без мемоизации: ~1-2 секунды (и экспоненциальный рост)
• fibonacci(40) с мемоизацией: ~0.001 секунды (линейное время)

Часть 8. Продвинутые паттерны рекурсии

8.1 Взаимная рекурсия

8.2 Глубокое копирование (через рекурсию)

8.3 Парсинг вложенных структур

Часть 9. Подводные камни

Камень #1: Забытый базовый случай

Камень #2: Рекурсия без изменяющегося аргумента

Камень #3: Рекурсия в асинхронном коде

Часть 10. Реальный кейс: Поиск в глубину на графе

Итог: Манифест рекурсии

1. Рекурсия - это функция, которая вызывает саму себя.
2. Два обязательных компонента: базовый случай (остановка) и рекурсивный случай (изменение аргументов).
3. Стек вызовов - структура LIFO, которая хранит информацию о вызовах.
4. Переполнение стека - когда глубина рекурсии превышает лимит (обычно 10 000+).
5. Рекурсия vs итерация: рекурсия лучше для древовидных структур, итерация - для линейных.
6. Мемоизация - кэширование результатов для оптимизации повторяющихся вызовов.
7. Хвостовая рекурсия - оптимизация, которая не увеличивает стек (но работает не везде).
8. Любую рекурсию можно превратить в итерацию с помощью ручного стека.

Финальный тест (что выведет?):

Ответы:

• mystery(48, 18) - алгоритм Евклида (НОД). 48 % 18 = 12, 18 % 12 = 6, 12 % 6 = 0, результат 6.
• trace(3) - 3, 2, 1, 1, 2, 3 (сначала вниз, потом вверх).

Рекурсия - это мощный инструмент, который делает сложные задачи простыми. Она требует понимания стека и ограничений, но когда вы её освоите, вы сможете решать задачи, которые итеративным способом были бы громоздкими и запутанными. Используйте рекурсию там, где она естественна (деревья, графы, алгоритмы "разделяй и властвуй"), и избегайте там, где глубина может быть слишком большой. И никогда не забывайте базовый случай. Иначе рекурсия уйдёт в бесконечность, и вы никогда не выйдете из лифта.