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

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

Как устроена рекурсивная функция

Любая корректная рекурсивная функция состоит из двух частей. Базовый случай возвращает ответ сразу, без новых вызовов. Рекурсивный случай сводит задачу к такой же, но меньшей, и вызывает для нее ту же функцию.

Классический пример - факториал. Произведение чисел от 1 до n можно записать как n, умноженное на факториал от n - 1. Остановка происходит на единице.

def factorial(n):
    """Возвращает n! для целого n >= 0."""
    if n <= 1:              # базовый случай
        return 1
    return n * factorial(n - 1)  # рекурсивный случай

print(factorial(10))  # 3628800

Условие n <= 1 надежнее, чем n == 1: оно корректно обрабатывает ноль (0! = 1). Если передать отрицательное число в версию с проверкой на равенство, функция никогда не дойдет до остановки.

Что происходит при вызове

Каждый вызов функции получает свой кадр в стеке: в нем хранятся локальные переменные и место, куда нужно вернуть результат. Когда factorial(4) вызывает factorial(3), первый кадр ждет ответа и не завершается.

factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * (3 * (2 * 1))
= 24

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

Как увидеть порядок вызовов

Чтобы понять чужую рекурсивную функцию, полезно вывести уровень вложенности. Отступ наглядно показывает спуск и подъем по стеку.

def countdown(n, depth=0):
    print("  " * depth + f"вход n={n}")
    if n > 0:
        countdown(n - 1, depth + 1)
    print("  " * depth + f"выход n={n}")

countdown(2)

Глубина рекурсии и RecursionError

Интерпретатор CPython ограничивает число вложенных вызовов, чтобы программа не обрушила процесс переполнением стека. Текущий лимит возвращает sys.getrecursionlimit(), по умолчанию это 1000. При превышении выбрасывается исключение RecursionError: maximum recursion depth exceeded.

import sys

print(sys.getrecursionlimit())  # 1000

def endless():
    return endless()

try:
    endless()
except RecursionError as e:
    print("Ошибка:", e)

Лимит можно поднять через sys.setrecursionlimit(5000), но это лечит симптом. Слишком большое значение приводит к аварийному завершению интерпретатора без понятного сообщения. Python также не выполняет оптимизацию хвостовой рекурсии: даже если рекурсивный вызов стоит последним, новый кадр все равно создается. Поэтому для глубины в десятки тысяч уровней правильнее переписать алгоритм на цикл.

Классические примеры

Рекурсия естественно ложится на задачи, где данные сами вложены друг в друга: деревья, каталоги, выражения, вложенные списки.

Числа Фибоначчи с кешем

Прямолинейная версия вычисляет одни и те же значения много раз и работает экспоненциально долго: fib(35) займет несколько секунд. Декоратор functools.cache запоминает результаты, и время становится линейным. О том, как устроены такие обертки, рассказано в статье про декораторы.

from functools import cache

@cache
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(80))  # 23416728348467685

Сумма вложенного списка

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

def deep_sum(items):
    total = 0
    for item in items:
        if isinstance(item, list):
            total += deep_sum(item)
        else:
            total += item
    return total

print(deep_sum([1, [2, 3], [4, [5, [6]]]]))  # 21

Обход дерева каталогов

Файловая система - тоже дерево. Функция печатает содержимое папки и спускается в каждую вложенную.

from pathlib import Path

def walk(path, level=0):
    for p in sorted(path.iterdir()):
        print("  " * level + p.name)
        if p.is_dir():
            walk(p, level + 1)

walk(Path("."))

Рекурсия или цикл

Любую рекурсию можно переписать итеративно, используя цикл и, при необходимости, собственный стек в виде списка. Выбор зависит от задачи.

Тот же факториал через цикл while или for работает быстрее и не упирается в лимит. А в стандартной библиотеке уже есть готовая функция math.factorial().

def factorial_loop(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

print(factorial_loop(5000) > 0)  # True, без RecursionError

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

Короткие ответы на вопросы, которые чаще всего задают о рекурсии.

Что такое базовый случай?

Это условие, при котором функция возвращает результат без нового рекурсивного вызова. Без него вызовы продолжаются до RecursionError.

Как увеличить максимальную глубину рекурсии?

Вызовите sys.setrecursionlimit(n) до запуска функции. Поднимайте значение умеренно: при очень большом лимите процесс может аварийно завершиться из-за переполнения системного стека.

Есть ли в Python хвостовая рекурсия?

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

Может ли лямбда-функция быть рекурсивной?

Технически да, если присвоить ее имени и обращаться к этому имени внутри: f = lambda n: 1 if n <= 1 else n * f(n - 1). На практике рекурсию пишут через def, так ее проще читать и отлаживать.