ЯдроКодаподготовка к экзаменам
Учебная платформа

Загружаем материалы

Подготавливаем материалы и навигацию по разделу.

Рекурсия в Python: функция вызывает саму себя

Автор: · Обновлено

Рекурсивная функция решает задачу через более простой экземпляр самой себя. Ей нужны базовый случай, который возвращает ответ без нового вызова, и шаг, приближающий данные к базе. Иначе стек вызовов растёт до RecursionError.

Сумма от 1 до n

def recursive_sum(number):
    if number == 0:
        return 0
    return number + recursive_sum(number - 1)


print(recursive_sum(4))

Результат:

10

Вызовы доходят 4 → 3 → 2 → 1 → 0. Затем ответы возвращаются в обратном порядке: 0, 1, 3, 6, 10.

Контракт входа

Для отрицательного числа шаг number - 1 никогда не достигнет нуля. Функция должна либо проверять number >= 0, либо иметь другой базовый случай, соответствующий задаче. Рекурсия также ограничена глубиной Python, поэтому длинный простой цикл безопаснее для больших n.

Типичная ошибка — забыть return перед рекурсивным выражением. Внутренний вызов вычислится, но внешний вернёт None. Другая ошибка — вызвать функцию с тем же аргументом без уменьшения.

Трассировка стека

Добавьте print('enter', number) перед if и print перед возвратом, используя временную переменную result. Проследите порядок для n = 3. Затем реализуйте factorial с базой 0! = 1 и assert для 0, 1 и 5. Сравните с циклической версией и объясните, где хранится промежуточное состояние в каждом варианте.

Когда цикл надёжнее рекурсии

Реализуйте сумму от 1 до n рекурсивно и циклом, затем проверьте одинаковый результат на малых n. Попробуйте большое значение и наблюдайте ограничение глубины рекурсии, не увеличивая его без необходимости. Для дерева каталогов или вложенной структуры рекурсивная форма может естественно повторять данные; для линейного счётчика цикл проще и безопаснее. Нарисуйте стек трёх вызовов с локальными number и ожидающим выражением. В заключении выберите реализацию не по длине кода, а по форме задачи, ограничению глубины и понятности состояния.

Практикум: база рекурсии и сравнение с циклом

Реализуйте сумму от 1 до n рекурсивно и циклом. Проверьте 0, 1 и 5, заранее определив поведение отрицательного аргумента. Нарисуйте стек для sum_to(3): локальное n и ожидающее сложение на каждом уровне. Удалите базу и объясните бесконечное углубление до RecursionError. Затем попробуйте большое значение и сравните ограничения двух версий. Для линейного счётчика выберите цикл, а рекурсию оставьте примером структуры вызовов.

Контрольная точка

Какие две части обязательны: базовый случай и переход к меньшей задаче? Покажите, что аргумент действительно приближается к базе на каждом вызове.

Частые вопросы

Можно ли просто увеличить предел рекурсии?

Технически можно, но это увеличивает риск переполнения стека и обычно не исправляет неверный алгоритм. Сначала выбирают итеративное решение или устраняют повторные вызовы; предел меняют только при обоснованной глубине.

Источники