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

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

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

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

Заключение

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

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

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

• 4 базовых функции для работы с файлами в Node.js
• 7 советов изучающему Vue.js новичку
• Больше JS, чем React: как фреймворк использует возможности языка
• JS-гайд: основные концепции JavaScript с примерами кода
• Лучшие фреймворки Node.js в 2021 году