Перевод публикуется с сокращениями, автор оригинальной статьи Dave Gray.
Рекурсия – это тема, которую программисты понимают не сразу, но это не должно вызывать страх или беспокойство.
В информатике рекурсия – это метод решения задачи, процесс, которого зависит от решений меньших экземпляров одной и той же задачи.
Вы можете применить рекурсию в коде, создав функцию, которая вызывает саму себя.
Любая функция с циклом может быть рекурсивной
Вот функция под названием countToTen, которая использует цикл while для вывода каждого числа от одного до десяти:
Можно написать ту же функцию с рекурсией вместо цикла.
Обратите внимание, что рекурсивные функции состоят из двух частей:
- функция вызывает саму себя (recursive call);
- по крайней мере, одно условие для выхода из рекурсии (base case).
Это не значит, что всегда следует заменять циклы рекурсией. Есть случаи, когда ее использование является лучшим вариантом и наоборот.
Зачем использовать рекурсию
Меньше строк кода
Применение рекурсии обычно приводит к решению с меньшим количеством строк кода, чем в решении без рекурсии.
Более элегантный код
В дополнение к меньшему количеству строк кода, рекурсивные решения, как правило, более приятны для просмотра. Другими словами, рекурсивные решения обычно считаются элегантными.
Улучшенная читабельность
Пункты 1 и 2 обычно объединяются, чтобы образовать следующую причину, которая заключается в улучшенной читабельности кода. Всегда помните, что вы пишете код не только для себя, но и для разработчиков, которые придут после вас и должны понимать ваш код.
Причины не использовать рекурсию
Потеря производительности
Повторные вызовы функций не так эффективны и производительны, как применение цикла. Не следует отдавать предпочтение рекурсии, просто потому что так можно.
Проблемы с отладкой
Логику рекурсии не всегда легко отследить, что может значительно затруднить отладку кода.
Что с читаемостью?
Улучшение читабельности совсем не гарантируется при использовании рекурсии – все зависит от ситуации. Вы должны оценить читаемость, и, если она страдает от применения этого метода, рекурсию лучше не использовать.
Рекурсия в примерах
В одной из таких задач необходима функция, возвращающая x чисел последовательности Фибоначчи. В этой последовательности берутся два предыдущих числа, чтобы вычислить следующий член ряда. Вот так выглядят первые десять чисел:
[0,1,1,2,3,5,8,13,21,34]
Можно написать эту функцию без рекурсии:
А вот рекурсивная версия той же функции:
Рекурсивная функция содержит меньше строк кода, но нет уверенности в том, что он обладает элегантностью и удобочитаемостью.
Рассмотрим другую ситуацию, на которую рекурсия оказывает большее влияние. Очередной фаворит на интервью пишет функцию, возвращающую n-е число в последовательности Фибоначчи. Поэтому, если функция получает 10 в качестве параметра, она должна вернуть 34.
Без использования рекурсии возможное решение выглядит следующим образом:
Однако с рекурсией решение намного меньше и аккуратнее:
Обратите внимание, как return вызывает функцию дважды.
Чтобы подчеркнуть улучшение, рассмотрим ту же рекурсивную функцию, написанную одной строкой (в браузере может получиться 2 строки, но на самом деле она одна):
Описанное ранее рекурсивное решение превратилось из четырех строк кода в одну. Для вас это более читабельно? Вы все еще улавливаете логику?
Ваш ответ будет зависеть от текущего уровня ваших знаний. В однострочном решении используется тернарный оператор: функция со стрелкой без скобок, которая также подразумевает оператор return, и как раньше применяется рекурсия. Это не значит, что в приведенном выше решении с одной строкой нет ничего плохого.
На самом деле эта функция элегантна, удобочитаема и очень эффективна, если вы понимаете логику, лежащую в ее основе.
Если вы работаете в команде, для нее может быть создано руководство по стилю написания. Если функция с одной строкой предпочтительнее, используйте этот подход. Если вы предпочитаете более продуманный и последовательный стиль, эти решения полностью ситуативны.
Заключение
- Рекурсия может показаться страшной, но это не обязательно так.
- Можно разбить понятие рекурсии на простые определения.
- Не используйте силу рекурсии только потому что можете.
- Решение об использовании рекурсии в коде следует основывать на эффективности, производительности, элегантности и удобочитаемости.
Если вам интересно, где рекурсия может быть применена в реальном мире, вместо того, чтобы отвечать на вопросы интервью с последовательностью Фибоначчи, автор материала подготовил туториал, где глубже разбирает приведенные примеры и демонстрирует некоторые случаи из практики. Удачи в обучении!
Дополнительные материалы:
Как часто вы используете рекурсию?