Мыслить рекурсивно: рекурсия в Python
Функция, которая решает задачу, вызывая уменьшенную копию самой себя
- дать определение рекурсии и различать базовый случай и рекурсивный случай,
- проследить, как стек вызовов растёт и разворачивается во время рекурсивного вызова,
- писать классические рекурсии: факториал, Фибоначчи, сумму списка и обход каталогов,
- решать, когда рекурсия читается лучше цикла, а когда цикл безопаснее,
- объяснить предел рекурсии в Python и почему глубокая рекурсия вызывает
RecursionError.
1. Что такое рекурсия
Вы уже пишете функции, которые вызывают другие функции. Рекурсия — это просто функция, которая вызывает саму себя. Звучит как замкнутый круг, и так бы и было, если бы каждый вызов не работал над меньшей частью задачи — до тех пор, пока часть не станет настолько маленькой, что ответ очевиден и новый вызов не нужен.
Представьте задачу, определённую через саму себя. «Факториал n — это n, умноженное на факториал n - 1». Это предложение описывает большую задачу (факториал n) через меньшую (факториал n - 1). Рекурсия превращает это самоссылающееся описание прямо в код.
def factorial(n):
if n == 0: # базовый случай: умножать больше нечего
return 1
return n * factorial(n - 1) # рекурсивный случай: меньшая задача
print(factorial(4)) # 24В последней строке функция ссылается на саму себя. Цикла нет, но она перемножает 4 * 3 * 2 * 1. Хитрость в том, что каждый вызов ждёт завершения меньшего вызова, прежде чем выполнить своё умножение.