Рекурсия

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

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

Базовый случай — это условие, при котором рекурсия перестаёт вызывать саму себя и начинает возвращать результат. Рекурсия работает по принципу «разделяй и властвуй»: задача разбивается на меньшие копии самой себя. Но в какой-то момент этот процесс должен остановиться — иначе не будет точки входа в обратный путь.

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

Факториал числа n — это произведение всех натуральных чисел от 1 до n.
Обозначается как n!
Пример: 5! = 5 × 4 × 3 × 2 × 1 = 120

Рекурсивное определение:
n! = n × (n-1)!
Базовый случай: 0! = 1

Реализация:

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

console.log(factorial(5)); // 120

Здесь factorial(5) вызывает factorial(4), который вызывает factorial(3) и так далее, пока не дойдёт до factorial(1). После этого цепочка возвратов начинает вычислять результат снизу вверх.

Ограничения

Каждый рекурсивный вызов занимает память в стеке вызовов. Если рекурсия слишком глубокая — стек переполняется, и браузер или приложение падает с ошибкой Stack Overflow.

Пример опасного случая:

function infiniteRecursion() {
  return infiniteRecursion(); // вызов без условия остановки
}

infiniteRecursion(); // приведёт к Stack Overflow

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

Используйте рекурсию только тогда, когда она делает код понятнее. В большинстве случаев лучше заменять её циклами — они эффективнее и безопаснее.