Что такое рекурсия и когда её использовать вместо цикла?

Определение

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

Любая рекурсивная функция состоит из двух частей:

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

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

Как это работает «под капотом»

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

Если базовый случай отсутствует или недостижим, произойдёт переполнение стека — RangeError: Maximum call stack size exceeded.

Когда рекурсия лучше цикла

• Структура данных сама по себе рекурсивная — деревья, графы, вложенные объекты, DOM.
• Алгоритм естественно описывается через разбиение на подзадачи — быстрая/слиянием сортировка, обход дерева, backtracking, поиск с возвратом.
• Рекурсивный код читается проще, чем эквивалентный цикл с ручным стеком/очередью.

function sumTree(node) {
  if (!node) return 0; // базовый случай — пустой узел
  return node.value + sumTree(node.left) + sumTree(node.right);
}

Когда цикл предпочтительнее

• Задача линейна и не требует запоминания промежуточных состояний — суммирование, перебор массива, поиск максимума.
• Важна память: каждый рекурсивный вызов — это кадр стека, то есть O(n) дополнительной памяти против O(1) у цикла.
• Глубина стека в JavaScript ограничена (обычно несколько тысяч вызовов), а хвостовая рекурсия описана в спецификации ES6, но реально не оптимизируется большинством движков, включая V8 — поэтому полагаться на неё нельзя.

Пример: рекурсия vs цикл для суммы массива

// рекурсивно — красиво, но расходует стек на больших массивах
function sumRec(arr, i = 0) {
  if (i === arr.length) return 0;
  return arr[i] + sumRec(arr, i + 1);
}

// итеративно — O(1) памяти, безопасно для больших массивов
function sumLoop(arr) {
  let total = 0;
  for (const n of arr) total += n;
  return total;
}

Как снизить риски рекурсии

• Преобразовать рекурсию в итеративную форму с собственным стеком (массивом), если глубина непредсказуема.
• Использовать мемоизацию, чтобы сократить число вызовов (актуально для чисел Фибоначчи и похожих задач).
• Помнить, что движки JS не гарантируют оптимизацию хвостовых вызовов — для больших n безопаснее цикл.

Итог

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