eFusion 12 мая 2021

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

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

Работа мечты в один клик 💼

Работа в Сбере: пройди собеседование и получи оффер за 15 минут

💭Мечтаешь работать в Сбере, но не хочешь проходить десять кругов HR-собеседований? Теперь это проще, чем когда-либо!

💡AI-интервью за 15 минут – и ты уже на шаг ближе к своей новой работе.

Как получить оффер?
📌 Зарегистрируйся
📌 Пройди AI-интервью
📌 Получи обратную связь сразу же!

HR больше не тянут время – рекрутеры свяжутся с тобой в течение двух дней! 🚀

Реклама. ПАО СБЕРБАНК, ИНН 7707083893. Erid 2VtzquscAwp

Перевод публикуется с сокращениями, автор оригинальной статьи 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, и как раньше применяется рекурсия. Это не значит, что в приведенном выше решении с одной строкой нет ничего плохого.

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

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

Заключение

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

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

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

Источники

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

ЛУЧШИЕ СТАТЬИ ПО ТЕМЕ