Рекурсия в JavaScript: базовый случай, стек вызовов и практические примеры

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

У корректной рекурсии есть две обязательные части:

1. базовый случай, который завершает вызовы;
2. рекурсивный шаг, который приближает данные к базовому случаю.

Без них функция будет вызывать себя до переполнения стека.

Простой пример: сумма чисел

function sumTo(number) {  if (!Number.isInteger(number) || number < 0) {    throw new TypeError('Ожидается неотрицательное целое число');  }​  if (number === 0) {    return 0;  }​  return number + sumTo(number - 1);}​console.log(sumTo(4)); // 10​

Для sumTo(4) цепочка выглядит так:

sumTo(4)4 + sumTo(3)4 + 3 + sumTo(2)4 + 3 + 2 + sumTo(1)4 + 3 + 2 + 1 + sumTo(0)​

При 0 начинается возврат результатов. Проверка аргумента предотвращает бесконечный уход в отрицательные числа и странное поведение с дробями.

Однако для такой задачи цикл проще и выдерживает большие значения:

function sumToIterative(number) {  if (!Number.isInteger(number) || number < 0) {    throw new TypeError('Ожидается неотрицательное целое число');  }​  let result = 0;​  for (let current = 1; current <= number; current += 1) {    result += current;  }​  return result;}​

Рекурсия — инструмент, а не цель.

Что происходит со стеком вызовов

JavaScript сохраняет состояние каждого незавершённого вызова в стеке. Пока внутренний вызов не вернул результат, внешний ждёт.

Максимальная глубина зависит от движка и окружения. Код вроде этого рано или поздно завершится ошибкой RangeError:

function loopForever() {  return loopForever();}​loopForever();​

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

Обход дерева категорий

const categories = [  {    name: 'Frontend',    children: [      { name: 'HTML', children: [] },      { name: 'CSS', children: [] },    ],  },  {    name: 'Backend',    children: [      { name: 'PHP', children: [] },    ],  },];​

Соберём плоский список названий:

function collectNames(nodes, result = []) {  for (const node of nodes) {    result.push(node.name);    collectNames(node.children, result);  }​  return result;}​console.log(collectNames(categories));// ['Frontend', 'HTML', 'CSS', 'Backend', 'PHP']​

Базовый случай здесь не записан отдельным if: для пустого массива цикл не выполняется, и функция сразу возвращает result. Каждый вызов получает более глубокий и в конечном итоге пустой список.

Поиск узла

function findCategory(nodes, targetName) {  for (const node of nodes) {    if (node.name === targetName) {      return node;    }​    const found = findCategory(node.children, targetName);    if (found) {      return found;    }  }​  return null;}​console.log(findCategory(categories, 'PHP'));​

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

Защита от циклических ссылок

Не каждое «дерево» действительно является деревом. В графе один объект может вести обратно к уже посещённому:

function walkGraph(node, visited = new Set()) {  if (visited.has(node)) {    return;  }​  visited.add(node);  console.log(node.name);​  for (const child of node.children) {    walkGraph(child, visited);  }}​

Set предотвращает повторный обход и бесконечный цикл. Для данных из внешнего источника также проверяйте форму объекта до доступа к children.

Итеративный обход глубокого дерева

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

function collectNamesIterative(nodes) {  const stack = [...nodes].reverse();  const result = [];​  while (stack.length > 0) {    const node = stack.pop();    result.push(node.name);​    for (let index = node.children.length - 1; index >= 0; index -= 1) {      stack.push(node.children[index]);    }  }​  return result;}​

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

Когда рекурсия уместна

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

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

Что запомнить

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

report Сообщить об ошибке в статье