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

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

Обязательные части

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

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

Где удобна

• Обход древовидных структур (DOM, файловая система, JSON).
• Разбиение задач: сортировки (quicksort), обход графов.

function countNodes(node) {
  let count = 1;
  for (const child of node.children) {
    count += countNodes(child);
  }
  return count;
}

Ограничения

• Каждый вызов занимает кадр в стеке → риск RangeError: Maximum call stack size exceeded при большой глубине.
• Глубокую рекурсию часто переписывают в цикл или используют стек-структуру.

Рекурсия против итерации

Рекурсия читабельнее для деревьев; итерация экономнее по памяти и без риска переполнения стека.

Коротко для собеседования

Рекурсия — функция вызывает себя, обязательно имея базовый случай и рекурсивный шаг. Удобна для деревьев и «разделяй и властвуй», но ограничена размером стека вызовов.