Когда мы пишем рекурсивные функции, нас учат делать «прыжок веры» — доверять, что вызов функции с меньшим аргументом сработает правильно.
👉 Вместо того чтобы держать в голове всю цепочку вызовов, мы опираемся на результат подзадачи и сосредотачиваемся только на текущем шаге.
Пример — факториал:
def factorial(n):
if n == 0:
return 1
# leap of faith: верим, что factorial(n-1) работает правильно
return n * factorial(n - 1)
print(factorial(5)) # 120
Здесь мы не проверяем вручную все вызовы
factorial(n-1). Мы просто верим, что они дадут верный результат, и используем его.Пять правил для «прыжка веры»:
1️⃣ Определите типы параметров и возвращаемого значения.
2️⃣ Сначала реализуйте базовый случай.
3️⃣ Сделайте «прыжок веры» — предположите, что рекурсивный вызов магически возвращает правильный результат, и напишите рекурсивный случай.
4️⃣ Ограничение 1: аргумент рекурсивного вызова не может быть исходным аргументом.
5️⃣ Ограничение 2: аргумент рекурсивного вызова всегда должен приближаться к базовому случаю.
Следуя этим правилам, рекурсия становится инструментом, которому можно доверять, а не головоломкой.
🔗 Полная статья о том, как писать рекурсивные функции эффективно.
🐸 Библиотека питониста
#буст