Перевод публикуется с сокращениями, автор оригинальной статьи 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, и как раньше применяется рекурсия. Это не значит, что в приведенном выше решении с одной строкой нет ничего плохого.
На самом деле эта функция элегантна, удобочитаема и очень эффективна, если вы понимаете логику, лежащую в ее основе.
Если вы работаете в команде, для нее может быть создано руководство по стилю написания. Если функция с одной строкой предпочтительнее, используйте этот подход. Если вы предпочитаете более продуманный и последовательный стиль, эти решения полностью ситуативны.
Заключение
- Рекурсия может показаться страшной, но это не обязательно так.
- Можно разбить понятие рекурсии на простые определения.
- Не используйте силу рекурсии только потому что можете.
- Решение об использовании рекурсии в коде следует основывать на эффективности, производительности, элегантности и удобочитаемости.
Если вам интересно, где рекурсия может быть применена в реальном мире, вместо того, чтобы отвечать на вопросы интервью с последовательностью Фибоначчи, автор материала подготовил туториал, где глубже разбирает приведенные примеры и демонстрирует некоторые случаи из практики. Удачи в обучении!
Дополнительные материалы:
Как часто вы используете рекурсию?