Объяснение рекурсии на примерах

Перевод статьи «Recursion Explained (with Examples)».

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

function understandRecursion(doIUnderstandRecursion) {
    const recursionAnswer = confirm('Do you understand recursion?');
    if(recursionAnswer === true) { // базовый случай
        return true;
    }
    understandRecursion(recursionAnswer); // рекурсивный вызов
}

Обратите внимание на базовый случай и рекурсивный вызов приведенном выше примере. Именно они и делают этот алгоритм рекурсивным.

В рекурсивных функциях обязательно должен быть базовый случай — условие, при котором НЕ совершается рекурсивный вызов.

Я думаю, что лучший способ объяснить рекурсию — обратиться к примерам, так что давайте рассмотрим часто встречающиеся задачи.

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

Вычисление факториала числа — распространенный пример задач, которые можно решить рекурсивно.

Напомним, что факториал числа n обозначается как n! и является произведением всех чисел от 0 до n. То есть, 5! равно 5*4*3*2*1, что в результате дает 120.

Давайте сначала посмотрим итеративное решение:

function factorial(num) {
    let total = 1;
    for(let n = num; n < 1; n--) {
        total *= n;
    }
    return total;
}

Это решение хорошее, но мы попробуем сделать то же самое при помощи рекурсии.

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

1. Мы знаем, что factorial(5) = 5 * factorial(4), или 5! = 5 * 4!.
2. Продолжая этот логический ряд, можно сказать, что factorial(5) = 5 * (4 * factorial(3)), или 5 * (4 * (3 * factorial(2)). И так далее…
3. …Пока не дойдем до 5 * 4 * 3 * 2 * 1. На этом этапе у нас останется только одна подзадача — найти 1!.
4. factorial(1) и factorial(0) всегда равны 1, так что это и будет наш базовый случай.

Используя такой подход, мы можем написать рекурсивное решение нашей задачи:

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

Пример 2: последовательность Фибоначчи

Еще одна задача, которую можно решить рекурсивно, это задача с числами Фибоначчи. Напомним, что последовательность Фибоначчи это ряд чисел 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 и так далее.

Все эти числа укладываются в определенный шаблон: каждое число равно сумме двух предыдущих. То есть, 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5 и т. д.

Другими словами, число Фибоначчи на позиции n (когда n > 2) это сумма числа Фибоначчи на позиции (n - 1) и числа Фибоначчи на позиции (n - 2).

Опять же, я думаю, будет полезным привести сначала итеративное решение:

function fibonacci(n) {
    if(n === 0) return 0;
    if(n === 1) return 1;

    let fibNMinus2 = 0;
    let finNMinus1 = 1;
    let fibN = n;

    for(let i = 2; i <= n; i++) { // n >= 2
        fibN = fibNMinus1 + fibNMinus2; // f(n-1) + f(n-2)
        fibNMinus2 = fibNMinus1;
        fibNMinus1 = fibN;
    }
    return fibN;
}

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

function fibonacci(n) {
    if(n === 0) return 0; // базовый случай 1
    if(n === 1) return 1; // базовый случай 2

    return fibonacci(n - 1) + fibonacci(n - 2); // рекурсивный вызов
}

При вызове функции fibonacci(5) будут сделаны следующие вызовы:

Фибоначчи с мемоизацией

Мне бы хотелось упомянуть еще один подход к решению этой задачи — мемоизацию. Мемоизация («запоминание») представляет собой технику оптимизации, при которой сохраняются результаты предыдущих вычислений (это похоже на кеширование). Благодаря этой технике мы можем ускорить работу нашего рекурсивного решения.

Если вы посмотрите на приведенную выше схему вызовов рекурсивной функции для вычисления fibonacci(5), вы увидите, что fibonacci(3) вычислялось дважды. Поэтому мы можем сохранить результат первого вычисления, чтобы при втором случае воспользоваться уже готовым ответом.

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

function fibonacci(n) {
    const memo = [0, 1]; // здесь кешируются все вычисленные результаты
    const fib = (n) => {
        if(memo[n] != null) return memo[n]; // базовый случай
        return memo[n] = fib(n - 1, memo) + fib(n - 2, memo); // рекурсивный вызов
    };
        return fib(n);
}

Зачем использовать рекурсию?

Честно говоря, рекурсивное решение практически всегда медленнее итеративного. Но при этом рекурсивные решения куда проще читать (вспомните пример с решениями по числам Фибоначчи), плюс мемоизация позволяет сократить отставание в скорости. В целом рекурсия проще для понимания, к тому же такие решения требуют меньше кода.

Заключение

Теперь, когда мы разобрали парочку примеров, я надеюсь, что вам стало легче разобраться в теме рекурсии и понять, зачем вообще ее использовать.

[customscript]techrocks_custom_after_post_html[/customscript]

[customscript]techrocks_custom_script[/customscript]