Рекурсия

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

Функция вызывает себя

Рекурсивная функция в своём теле вызывает саму себя с другим аргументом. Вот обратный отсчёт:

function countdown(n) {
  if (n === 0) {
    return;
  }
  console.log(n);
  countdown(n - 1);
}
 
countdown(3);
// 3
// 2
// 1

Каждый вызов выводит число и передаёт следующему вызову число на единицу меньше.

Базовый случай

Условие, при котором функция перестаёт вызывать себя, называют базовым случаем. В примере выше это n === 0: дойдя до нуля, функция просто завершается. Без базового случая рекурсия никогда бы не закончилась. Поэтому рекурсивную функцию начинают писать именно с него: сначала решают самый простой вариант задачи, а потом сводят к нему остальные.

Возврат результата

Рекурсивная функция может возвращать значение. Сумму чисел от 1 до n можно описать так: это n плюс сумма чисел от 1 до n - 1:

function sumTo(n) {
  if (n === 1) {
    return 1;
  }
  return n + sumTo(n - 1);
}
 
console.log(sumTo(4)); // 10

Вызов sumTo(4) превращается в 4 + sumTo(3), затем в 4 + 3 + sumTo(2) и наконец в 4 + 3 + 2 + 1.

Факториал

Классический пример рекурсии — факториал: произведение всех чисел от 1 до n. Факториал 5 равен 5 * 4 * 3 * 2 * 1:

function factorial(n) {
  if (n <= 1) {
    return 1;
  }
  return n * factorial(n - 1);
}
 
console.log(factorial(5)); // 120

Стек вызовов

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

Рекурсия или цикл

Любую рекурсию можно заменить циклом, и наоборот. Для простого счёта цикл понятнее и не расходует стек:

let result = 1;
 
for (let i = 2; i <= 5; i++) {
  result *= i;
}
 
console.log(result); // 120

Рекурсию выбирают, когда данные сами устроены рекурсивно — как дерево папок или вложенные комментарии.

Частая ошибка

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

function countdown(n) {
  countdown(n - 1); // нет условия выхода
}
 
countdown(3); // RangeError: Maximum call stack size exceeded

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