🌀 Что такое прыжок веры и зачем он нужен

Когда мы пишем рекурсивные функции, нас учат делать «прыжок веры» — доверять, что вызов функции с меньшим аргументом сработает правильно.

👉 Вместо того чтобы держать в голове всю цепочку вызовов, мы опираемся на результат подзадачи и сосредотачиваемся только на текущем шаге.

Пример — факториал:

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: аргумент рекурсивного вызова всегда должен приближаться к базовому случаю.

Следуя этим правилам, рекурсия становится инструментом, которому можно доверять, а не головоломкой.

🔗 Полная статья о том, как писать рекурсивные функции эффективно.

🐸 Библиотека питониста

#буст