Рекурсия

Представьте матрёшку. Чтобы добраться до самой маленькой куклы, вы открываете большую, а внутри — та же матрёшка, только меньше. Вы повторяете одно и то же действие, пока не дойдёте до цельной куклы, которая уже не открывается.

Некоторые задачи устроены так же: внутри задачи сидит та же задача, только меньше. Факториал числа n — произведение всех чисел от 1 до n. Его определяют двумя правилами:

• факториал нуля равен 1;
• факториал n равен n, умноженному на факториал n - 1.

Функция на JavaScript повторяет это определение, вызывая саму себя:

function factorial(n) {
    if (n === 0) {
        return 1;
    }
    return n * factorial(n - 1);
}

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

Давайте разберём, как считается factorial(5):

1. Вызов factorial(5) сразу ответа не знает. Он вызывает factorial(4) и ждёт результат, чтобы умножить его на 5.
2. factorial(4) так же поручает работу factorial(3), и так до factorial(0).
3. factorial(0) отвечает 1 сразу, никого не вызывая.
4. Ответы идут обратно, и программа печатает 120.

Две ветки рекурсивной функции

Рекурсия — это вызов функцией самой себя. Каждый вызов получает собственный параметр n, поэтому factorial(5), factorial(4) и остальные вызовы друг другу не мешают. В рекурсивной функции всегда две ветки.

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

factorial(0) возвращает 1 сразу, без нового вызова. Ветку, в которой функция завершается без рекурсии, называют базовым случаем. Это цельная кукла внутри матрёшки.

Без базового случая вызовы никогда не закончатся. Каждый рекурсивный вызов должен приближать аргумент к нему: здесь n уменьшается на 1.

Рекурсивный шаг

Строка return n * factorial(n - 1); вызывает ту же функцию с аргументом на единицу меньше. Вызов factorial(5) ждёт результата factorial(4), тот ждёт factorial(3), и так до factorial(0).

Дальше результаты возвращаются по цепочке: 1, 1, 2, 6, 24 и, наконец, 120. Здесь аналогия с матрёшкой заканчивается: куклу только открывают, а каждый вызов ещё и возвращает ответ тому, кто его ждёт.

Рекурсия удобна, когда задача определена через меньшую копию самой себя, как факториал или степень числа.

Стек вызовов

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

Стек похож на стопку тарелок:

• новый вызов кладёт тарелку сверху;
• завершённый вызов снимает верхнюю тарелку.

Нажимайте «Следующий шаг» и следите, как стопка рамок растёт до factorial(0), а потом разбирается сверху вниз. Виджет считает factorial(3), чтобы стопка поместилась на экране.

У factorial(5) стопка выше: в самой глубокой точке над записью скрипта лежат шесть вызовов, от factorial(5) до factorial(0).

Цикл вместо рекурсии

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

Он делает то же самое без новых записей в стеке. Произведение накапливает переменная result:

function factorialLoop(n) {
    let result = 1;
    for (let i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

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

Цикл не вызывает новых функций: переменные result и i меняются на месте. Сколько бы ни было шагов, стопка тарелок не растёт.

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

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

console.log(factorial(-1)); // ✗

RangeError: Maximum call stack size exceeded

Это сообщение Node.js и Chrome; Firefox пишет InternalError: too much recursion.

От -1 цепочка идёт к -2, -3 и дальше, а n === 0 не наступает никогда. Каждый вызов добавляет запись, пока стек не заполнится, и программа останавливается с ошибкой. Проверяйте, что базовый случай достижим из любого допустимого аргумента, а недопустимые аргументы отсекайте до рекурсии.

Этот вопрос часто задают на собеседовании: «Что будет, если у рекурсии нет базового случая или он недостижим?» Ответ: стек переполнится, и программа остановится с RangeError.

Главное

• Рекурсивная функция вызывает саму себя, и ей нужен базовый случай, который завершается без нового вызова.
• Каждый рекурсивный вызов должен приближать аргумент к базовому случаю.
• Каждый незавершённый вызов занимает запись в стеке вызовов, а размер стека ограничен.
• Для очень глубокой рекурсии вместо неё пишут цикл.