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

Рекурсия — фундаментальная концепция в JavaScript, которая позволяет функциям вызывать самих себя. Этот подход незаменим при решении задач, которые можно разбить на более простые повторяющиеся подзадачи. В данной статье представлен подробный обзор рекурсии: рассматриваются контекст выполнения, стек вызовов и применение рекурсии для обхода рекурсивных структур данных.

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

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

1. Базовый случай: условие, при котором функция прекращает вызывать себя и возвращает значение напрямую. Без базового случая функция вызывала бы себя бесконечно.
2. Рекурсивный случай: если базовый случай не выполнен, функция снова вызывает себя с меньшим или более простым аргументом, приближающим её к базовому случаю.

Важнейшее правило рекурсии: каждый рекурсивный вызов должен продвигаться к базовому случаю. Если этого не происходит, возникает бесконечная рекурсия и программа завершается ошибкой переполнения стека.

Вот минимальный практический пример — суммирование чисел от 1 до n:

Чтобы вычислить sumTo(5), функции нужен результат sumTo(4), которому нужен sumTo(3), и так далее вплоть до sumTo(1), который возвращает 1 напрямую. Затем цепочка разматывается: каждый вызов прибавляет своё число и передаёт результат вызвавшей его функции.

Ту же логику всегда можно реализовать с помощью цикла. Сравните рекурсивный вариант выше с итеративным:

Оба варианта дают одинаковый результат. Рекурсивный вариант короче и ближе к математическому определению; итеративный использует один вызов функции и фиксированный объём памяти. Подробное сравнение приведено в разделе Рекурсия vs итерация ниже.

Контекст выполнения и стек вызовов

Когда в JavaScript выполняется функция, движок создаёт контекст выполнения (его также называют стековым фреймом): внутреннюю запись, содержащую локальные переменные этого вызова, его параметры и точную строку, на которой сейчас находится выполнение.

Стек вызовов — это стек таких фреймов. Он работает по принципу «последним вошёл — первым вышел»:

• При вызове функции её фрейм помещается на вершину стека.
• Когда функция возвращает результат, её фрейм удаляется со стека, и управление возвращается к нижележащему фрейму — ровно в то место, где он остановился.

При рекурсии каждый вызов функции помещает на стек новый фрейм с собственной копией параметров. Так, sumTo(3) создаёт три стековых фрейма, прежде чем хотя бы один из них вернёт значение:

sumTo(1)   ← вершина стека, возвращает 1 первым
sumTo(2)
sumTo(3)   ← дно стека, исходный вызов, возвращает последним

Как только sumTo(1) достигает базового случая и возвращает результат, его фрейм удаляется, sumTo(2) продолжает выполнение и возвращает результат, затем sumTo(3). Именно поэтому глубина рекурсии напрямую определяет объём занятой памяти стека: n рекурсивных вызовов означает n одновременно живых фреймов.

Пример: Вложенные сны

Представьте ситуацию, в которой герой рассказа засыпает и видит сон, в котором он является другим персонажем, который тоже засыпает и видит сон о следующем персонаже, и так далее. Каждый уровень сна соответствует рекурсивному вызову, а пробуждение из каждого уровня — удалению контекста выполнения из стека вызовов.

В функции dream(level) базовый случай и рекурсивный случай чётко определены:

• Базовый случай: наступает при level === 0. Это условие, которое останавливает рекурсию, не давая ей продолжаться бесконечно. Когда level достигает 0, функция выводит «Wake up!» и прекращает рекурсивные вызовы.
• Рекурсивный случай: определён при level > 0. В этой ситуации функция выводит текущий level, а затем вызывает себя с level - 1, уменьшая level на единицу при каждом вызове. Это продолжается до тех пор, пока не будет выполнено условие базового случая.

Эти две части работают совместно, обеспечивая корректное выполнение функции и её завершение.

Рекурсивный обход

Рекурсивный обход — техника, которая часто применяется со структурами, содержащими несколько уровней вложенных объектов, например деревьями или каталогами файловой системы. Этот метод идеально подходит для операций вроде поиска или построения визуальной структуры из вложенных компонентов.

Пример: Обход файловой системы

Вот как можно использовать рекурсию для обхода файловой системы с выводом всех файлов в каждом каталоге:

В функции listFiles(directory) рекурсия осуществляет обход структуры каталогов:

• Базовый случай: интересно, что явно выраженного базового случая в виде условного оператора, завершающего рекурсию, здесь нет. Вместо этого рекурсия естественным образом останавливается, когда встречается каталог без подкаталогов (то есть directory.directories является пустым array). Это происходит потому, что метод forEach на пустом массиве не производит дальнейших рекурсивных вызовов.
• Рекурсивный случай: рекурсия явно вызывается строкой directory.directories.forEach(listFiles);. Это происходит, когда каталог содержит один или несколько подкаталогов, и listFiles вызывается рекурсивно для каждого из них. Каждый рекурсивный вызов обрабатывает файлы и каталоги внутри этого подкаталога, углубляясь в структуру до тех пор, пока подкаталоги не закончатся (неявный базовый случай).

Эта функция наглядно демонстрирует, как рекурсия позволяет перемещаться по сложным вложенным структурам, вызывая себя для обработки аналогичных задач на каждом уровне вложенности.

Рекурсивные структуры

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

Пример: Организационная схема

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

В функции showOrgChart(employee) рекурсия структурирована для визуализации организационной схемы:

• Базовый случай: как и в предыдущем примере с listFiles, базовый случай не задан явно в виде условной точки остановки. Вместо этого рекурсия естественно завершается, когда у сотрудника нет подчинённых (employee.subordinates является пустым массивом). Метод forEach не выполняет итераций для пустого массива, и дальнейших рекурсивных вызовов не происходит.
• Рекурсивный случай: рекурсивное поведение реализовано строкой employee.subordinates.forEach(showOrgChart). Это означает, что каждый раз, когда у сотрудника есть один или несколько подчинённых, функция рекурсивно вызывается для каждого из них. Рекурсия продолжается вниз по иерархии, выводя имя и должность каждого подчинённого, пока не будут достигнуты сотрудники без подчинённых (неявный базовый случай).

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

Рекурсия vs итерация

Любую рекурсивную функцию можно переписать в виде цикла, и любой цикл можно переписать в виде рекурсии. Выбор между ними — это компромисс:

Хорошее практическое правило: используйте рекурсию, когда сами данные рекурсивны (деревья, вложенные объекты, файловая система), и используйте цикл, когда нужно просто повторить шаг известное число раз. Факториал ниже по природе своей рекурсивен, но цикл справляется не хуже — и выдерживает значительно бо́льшие входные данные:

Переполнение стека и ограничения глубины

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

RangeError: Maximum call stack size exceeded

Две наиболее распространённые причины — отсутствующий или недостижимый базовый случай (бесконечная рекурсия) и законно глубокая рекурсия при работе с очень большим набором данных. В следующем примере базовый случай намеренно опущен, чтобы стек переполнился:

Чтобы избежать переполнения стека:

• Всегда включайте базовый случай, до которого рекурсия гарантированно дойдёт.
• Для очень глубоких или неограниченных задач преобразуйте рекурсию в цикл — у него нет подобного ограничения глубины.
• Для структур данных произвольной глубины рассмотрите использование явного стека (массива, в который вы делаете push/pop) вместо стека вызовов.

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

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

• Сортировки данных (например, сортировка слиянием или быстрая сортировка)
• Обхода деревьев, графов и вложенных итерируемых объектов
• Работы со сложными структурированными данными, такими как JSON или DOM

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

Связанные темы

• Функции JavaScript — как объявляются и вызываются функции.
• Функциональные выражения — функции, сохранённые в переменных, которые рекурсивные функции часто используют.
• Итерируемые объекты — рекурсивный обход естественным образом сочетается с итерируемыми данными.
• Циклы JavaScript — итеративная альтернатива рекурсии.

Заключение

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

Практика