Рекурсия в JS

В этой статье вы узнаете, как работает рекурсия в JavaScript.

Рекурсия — это процесс вызова функцией самой себя. Функция, которая в своем теле вызывает сама себя, называется рекурсивной функцией.

Синтаксис

function recurse() {
    // код функции
    recurse(); // функция вызывает сама себя
    // код функции 
}

recurse();

Здесь функция recurse() — рекурсивная функция, поскольку вызывает сама себя в своем теле.

Как это работает

Внутри рекурсивной функции обязательно должно находится условие выхода из рекурсии. Иначе функция будет вызывать саму себя бесконечно.

Как только условие выхода выполняется, функция перестает вызывать себя. 

Чтобы предотвратить бесконечную рекурсию, можно использовать оператор if...else (или аналогичный подход), в котором одна ветвь выполняет рекурсивный вызов, а другая — нет.

В общем случае это выглядит так:

function recurse() {
    if(условие) {
        recurse();
    }
    else {
        // остановить вызов recurse()
    }
}

recurse();

Пример 1. Выводим числа от n до 1

function countDown(number) {

    // вывод в консоль
    console.log(number);

    // уменьшаем значение на один
    const newNumber = number - 1;

    // условие выхода
    if (newNumber > 0) {
        countDown(newNumber);
    }
}

countDown(4);

Вывод

4
3
2
1

Как это работает

• Пользователь передает число в качестве аргумента при вызове функции. В нашем случае — 4.
• На каждой итерации значение числа уменьшается на 1.
• Функция countDown() вызывается до тех пор, пока число не станет положительным. newNumber > 0 — условие выхода из рекурсии.

Вот, как выглядят рекурсивные вызовы по шагам:

1. countDown(4) выводит 4 и вызывает countDown(3)
2. countDown(3) выводит 3 и вызывает countDown(2)
3. countDown(2) выводит 2 и вызывает countDown(1)
4. countDown(1) выводит 1 и вызывает countDown(0)
5. Текущее число — 0, поэтому newNumber > 0 = false. Выходим из рекусии.

Пример 2. Факториал с помощью рекурсии

function factorial(x) {

    // если число — ноль
    if (x === 0) {
        return 1;
    }

    //если число положительное
    else {
        return x * factorial(x - 1);
    }
}

const num = 3;

// вызов factorial(), если число неотрицательное 
if (num > 0) {
    let result = factorial(num);
    console.log(`Факториал ${num} равен ${result}`);

Вывод

Факториал 3 равен 6

Как это работает

• Когда функция factorial() вызывается с целым положительным аргументов, она рекурсивно вызывает саму себя, уменьшая число на 1.
• Этот процесс продолжается до тех пор, пока число не станет равным 1. Когда функция в очередной раз уменьшит число на 1, оно станет равно 0. Факториал нуля — 1 → вернется единица. 

Вот, как выглядят рекурсивные вызовы по шагам:

1. factorial(3) возвращает 3 * factorial(2)
2. factorial(2) возвращает 3 * 2 * factorial(1)
3. factorial(1) возвращает 3 * 2 * 1 * factorial(0)
4. factorial(0) возвращает 3 * 2 * 1 * 1