Рекурсия в Python

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

Эта глава охватывает:

• Как работает рекурсия и как выглядит стек вызовов
• Базовый случай и рекурсивный случай
• Классические рекурсивные задачи: факториал, числа Фибоначчи, возведение в степень, выравнивание вложенных списков
• Рекурсия против итерации — когда что выбирать
• Ограничение рекурсии в Python и способы его обойти
• Мемоизация с помощью functools.lru_cache

Как работает рекурсия

Когда функция вызывает саму себя, Python помещает новый фрейм стека в стек вызовов для каждого вызова. Каждый фрейм хранит свои собственные локальные переменные. Когда достигается базовый случай, фреймы начинают возвращаться в обратном порядке — последним вошёл, первым вышел — пока исходный вызов не получит окончательный ответ.

Корректная рекурсивная функция всегда состоит из двух частей:

Без базового случая (или когда он никогда не достигается) функция вызывает саму себя бесконечно, и Python генерирует RecursionError.

Простой пример: обратный отсчёт

Следующая функция ведёт обратный отсчёт от n до нуля, после чего выводит "Go!". Её легко отследить, так как каждый вызов уменьшает n на единицу, пока n <= 0.

def countdown(n):
    if n <= 0:         # base case
        print("Go!")
        return
    print(n)
    countdown(n - 1)   # recursive case

countdown(5)

Вывод:

5
4
3
2
1
Go!

Трассировка стека вызовов:

1. countdown(5) выводит 5, вызывает countdown(4)
2. countdown(4) выводит 4, вызывает countdown(3)
3. … и так далее …
4. countdown(0) выводит "Go!" и возвращает управление — начинается раскрутка стека

Факториал

Факториал числа n (записывается n!) — это произведение всех положительных целых чисел до n включительно. Он определяется рекурсивно следующим образом:

• 0! = 1 (базовый случай)
• n! = n × (n − 1)! (рекурсивный случай)

def factorial(n):
    if n == 0 or n == 1:   # base case
        return 1
    return n * factorial(n - 1)

print(factorial(5))    # 120
print(factorial(0))    # 1
print(factorial(10))   # 3628800

factorial(5) разворачивается следующим образом, прежде чем будет возвращено какое-либо значение:

factorial(5)
  5 * factorial(4)
        4 * factorial(3)
              3 * factorial(2)
                    2 * factorial(1)
                          1          ← base case

Затем умножения выполняются на обратном пути: 1 → 2 → 6 → 24 → 120.

Последовательность Фибоначчи

Последовательность Фибоначчи определяется так: каждое число является суммой двух предыдущих — 0, 1, 1, 2, 3, 5, 8, 13, …

def fibonacci(n):
    if n <= 0:   # base case
        return 0
    if n == 1:   # base case
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

for i in range(8):
    print(fibonacci(i), end=" ")
# Output: 0 1 1 2 3 5 8 13

Это корректное решение, но медленное для больших n — fibonacci(40) производит миллионы избыточных вызовов. Решение описано в разделе Мемоизация ниже.

Сумма элементов списка

Рекурсия естественным образом применяется к спискам: обработай первый элемент, затем рекурсивно обработай остаток.

def sum_list(lst):
    if not lst:              # base case — empty list
        return 0
    return lst[0] + sum_list(lst[1:])

print(sum_list([1, 2, 3, 4, 5]))   # 15
print(sum_list([]))                 # 0

lst[1:] создаёт новый список без первого элемента, уменьшая задачу на один элемент при каждом вызове.

Возведение числа в степень

def power(base, exp):
    if exp == 0:          # base case: anything to the power 0 is 1
        return 1
    return base * power(base, exp - 1)

print(power(2, 10))   # 1024
print(power(3, 4))    # 81
print(power(5, 0))    # 1

Выравнивание вложенного списка

Некоторые задачи являются по своей природе рекурсивными — они имеют одинаковую структуру на каждом уровне. Выравнивание произвольно вложенного списка — одна из них.

def flatten(lst):
    result = []
    for item in lst:
        if isinstance(item, list):
            result.extend(flatten(item))   # recurse into sublists
        else:
            result.append(item)
    return result

print(flatten([1, [2, 3], [4, [5, 6]], 7]))
# [1, 2, 3, 4, 5, 6, 7]

Это сложно реализовать чисто с помощью одной только итерации, поскольку глубина вложенности заранее неизвестна.

Рекурсия против итерации

Большинство рекурсивных алгоритмов можно переписать в виде итеративных циклов, и наоборот.

Итеративный факториал

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

print(factorial_iterative(5))   # 120

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

Ограничение рекурсии в Python

Python ограничивает стек вызовов 1 000 фреймами по умолчанию, чтобы предотвратить переполнение стека, которое могло бы вызвать сбой процесса.

import sys
print(sys.getrecursionlimit())   # 1000

Если ваша функция превысит этот лимит, вы увидите:

RecursionError: maximum recursion depth exceeded

Вы можете увеличить лимит с помощью sys.setrecursionlimit(n), но делайте это осторожно — очень глубокий стек может исчерпать системную память. Для по-настоящему глубокой рекурсии перепишите алгоритм итеративно или используйте генераторы Python для ручной эмуляции стека.

Мемоизация

Наивная рекурсивная реализация Фибоначчи работает экспоненциально медленно, поскольку решает одни и те же подзадачи снова и снова. Мемоизация кэширует результат каждого уникального вызова, чтобы он вычислялся лишь один раз.

Ручной кэш с помощью словаря

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 0:
        return 0
    if n == 1:
        return 1
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

print(fibonacci(10))   # 55
print(fibonacci(30))   # 832040

Использование functools.lru_cache

Стандартная библиотека предоставляет декоратор, который автоматически управляет кэшированием:

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(10))   # 55
print(fibonacci(50))   # 12586269025

@lru_cache превращает экспоненциальный алгоритм в линейный без каких-либо дополнительных изменений внутри тела функции. Это идиоматичный подход Python для мемоизации чистых рекурсивных функций.

Двоичный поиск (рекурсивный)

Двоичный поиск — классический алгоритм типа «разделяй и властвуй»: сравниваем целевое значение со средним элементом, затем рекурсивно обрабатываем левую или правую половину.

def binary_search(lst, target, low=0, high=None):
    if high is None:
        high = len(lst) - 1
    if low > high:        # base case: search space exhausted
        return -1
    mid = (low + high) // 2
    if lst[mid] == target:
        return mid
    elif lst[mid] < target:
        return binary_search(lst, target, mid + 1, high)
    else:
        return binary_search(lst, target, low, mid - 1)

nums = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(nums, 7))    # 3
print(binary_search(nums, 1))    # 0
print(binary_search(nums, 15))   # 7
print(binary_search(nums, 4))    # -1  (not found)

Распространённые ошибки

Отсутствующий базовый случай

# This will raise RecursionError
def broken(n):
    return n * broken(n - 1)   # no base case!

Всегда спрашивайте себя: «Какой самый простой входной аргумент должна обрабатывать эта функция, не вызывая себя?»

Бесконечная рекурсия из-за неверного базового случая

# factorial of a negative number loops forever
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)   # n goes -1, -2, -3 ...

# Fix: guard at the top
def factorial(n):
    if n < 0:
        raise ValueError("n must be non-negative")
    if n == 0:
        return 1
    return n * factorial(n - 1)

Изменяемый аргумент по умолчанию как кэш

Использование memo={} в качестве параметра по умолчанию удобно, но совместно использует состояние между всеми вызовами верхнего уровня. В продакшн-коде передавайте кэш явно или используйте @lru_cache.

Когда использовать рекурсию

Рекурсия естественно подходит для:

• Обхода деревьев и графов — списки директорий, обход DOM, деревья решений
• Алгоритмов «разделяй и властвуй» — сортировка слиянием, быстрая сортировка, двоичный поиск
• Математических определений — факториал, числа Фибоначчи, комбинаторика
• Поиска с возвратом — решение лабиринтов, судоку, генерация перестановок
• Вложенных структур данных — разбор JSON/XML, выравнивание вложенных списков

Для простых последовательных циклов или при большой глубине предпочтительнее циклы for или циклы while.

Связанные главы

• Функции Python — строительные блоки, на которых строится рекурсия
• Область видимости Python — понимание работы локальных переменных в каждом фрейме
• Цикл while в Python — итеративная альтернатива
• Генераторы Python — эффективные по памяти альтернативы для последовательностей
• Итераторы Python — протокол итерации, лежащий в основе модели циклов Python
• Python Try Except — корректная обработка RecursionError

Практика