Что такое рекурсия? Какие у неё правила? Для чего нужна?

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

Правила рекурсии:

• Должна быть базовая (терминальная) ветка, при достижении которой рекурсивные вызовы прекращаются.
• Каждый рекурсивный вызов должен приближать к базовому случаю, чтобы избежать бесконечной рекурсии.

Для чего нужна рекурсия:

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

Пример вычисления факториала:

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

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