eFusion 12 мая 2021

JavaScript

2207

∞ Рекурсия может показаться пугающей, но это необязательно

Любая концепция, которую мы не до конца понимаем, может поначалу пугать. Это касается и рекурсии, но не стоит ее бояться.

Перевод публикуется с сокращениями, автор оригинальной статьи Dave Gray.

Рекурсия – это тема, которую программисты понимают не сразу, но это не должно вызывать страх или беспокойство.

В информатике рекурсия – это метод решения задачи, процесс, которого зависит от решений меньших экземпляров одной и той же задачи.

Источник: Википедия.

Вы можете применить рекурсию в коде, создав функцию, которая вызывает саму себя.

Любая функция с циклом может быть рекурсивной

Вот функция под названием countToTen, которая использует цикл while для вывода каждого числа от одного до десяти:

const countToTen = (num = 1) => {
    while (num <= 10) {
        console.log(num);
        num++;
    }
}

countToTen();

Можно написать ту же функцию с рекурсией вместо цикла.

Обратите внимание, что рекурсивные функции состоят из двух частей:

функция вызывает саму себя (recursive call);
по крайней мере, одно условие для выхода из рекурсии (base case).

const countToTen = (num = 1) => {
    if (num > 10) return; //base case
    console.log(num);
    num++;
    countToTen(num); //recursive call
}

countToTen();

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

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

Рассмотрим некоторые причины с примерами использования рекурсии.

Меньше строк кода

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

Более элегантный код

В дополнение к меньшему количеству строк кода, рекурсивные решения, как правило, более приятны для просмотра. Другими словами, рекурсивные решения обычно считаются элегантными.

Улучшенная читабельность

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

Причины не использовать рекурсию

Потеря производительности

Повторные вызовы функций не так эффективны и производительны, как применение цикла. Не следует отдавать предпочтение рекурсии, просто потому что так можно.

Проблемы с отладкой

Логику рекурсии не всегда легко отследить, что может значительно затруднить отладку кода.

Что с читаемостью?

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

Рекурсия в примерах

Ситуации с рекурсией часто попадаются на собеседованиях, и многие кандидаты на них проваливаются.

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

[0,1,1,2,3,5,8,13,21,34]

Можно написать эту функцию без рекурсии:

const fibonacci = (num = 2, array = [0, 1]) => {
    while (num > 2) {
        const [nextToLast, last] = array.slice(-2);
        array.push(nextToLast + last);
        num -= 1;
    }
    return array;
}

console.log(fibonacci(10));

А вот рекурсивная версия той же функции:

const fibonacci = (num = 2, array = [0, 1]) => {
    if (num < 2) return array.slice(0, array.length - 1);
    const [nextToLast, last] = array.slice(-2);
    return fibonacci(num - 1, [...array, nextToLast + last]);
}

console.log(fibonacci(10));

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

Рассмотрим другую ситуацию, на которую рекурсия оказывает большее влияние. Очередной фаворит на интервью пишет функцию, возвращающую n-е число в последовательности Фибоначчи. Поэтому, если функция получает 10 в качестве параметра, она должна вернуть 34.

Без использования рекурсии возможное решение выглядит следующим образом:

const fibonacciPos = (pos = 1) => {
    if (pos < 2) return pos;
    const seq = [0, 1];
    for (let i = 2; i <= pos; i++) {
        const [nextToLast, last] = seq.slice(-2);
        seq.push(nextToLast + last);
    }
    return seq[pos];
}

console.log(fibonacciPos(10));

Однако с рекурсией решение намного меньше и аккуратнее:

const fibonacciPos = (pos = 1) => {
    if (pos < 2) return pos;
    return fibonacciPos(pos - 1) + fibonacciPos(pos - 2);
}

console.log(fibonacciPos(10));

Обратите внимание, как return вызывает функцию дважды.

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

Чтобы подчеркнуть улучшение, рассмотрим ту же рекурсивную функцию, написанную одной строкой (в браузере может получиться 2 строки, но на самом деле она одна):

const fibonacciPos= pos => pos < 2 ? pos : fibonacciPos(pos - 1) + fibonacciPos(pos - 2);

console.log(fibonacciPos(10));

Описанное ранее рекурсивное решение превратилось из четырех строк кода в одну. Для вас это более читабельно? Вы все еще улавливаете логику?

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

На самом деле эта функция элегантна, удобочитаема и очень эффективна, если вы понимаете логику, лежащую в ее основе.

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

Заключение

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

Если вам интересно, где рекурсия может быть применена в реальном мире, вместо того, чтобы отвечать на вопросы интервью с последовательностью Фибоначчи, автор материала подготовил туториал, где глубже разбирает приведенные примеры и демонстрирует некоторые случаи из практики. Удачи в обучении!

Дополнительные материалы:

Источники

https://www.freecodecamp.org/news/recursion-doesnt-have-to-be-scary/