Какое придел вложенности рекурсии в Python?

Предел вложенности рекурсии в Python

В Python существует жёсткое ограничение на глубину рекурсии, которое защищает программу от переполнения стека памяти.

1. Стандартный лимит рекурсии

По умолчанию Python устанавливает лимит на 1000 уровней рекурсии:

import sys

# Проверить текущий лимит
print(sys.getrecursionlimit())  # Обычно 1000

# Изменить лимит
sys.setrecursionlimit(2000)  # Увеличить до 2000

Этот лимит можно проверить и изменять, но нужно быть осторожным.

2. Почему существует ограничение?

Проблема переполнения стека:

# Опасная рекурсия без базового случая
def bad_recursion(n):
    return bad_recursion(n + 1)  # Бесконечная рекурсия!

try:
    bad_recursion(0)
except RecursionError as e:
    print(f"Ошибка: {e}")

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

3. Примеры хороших и плохих рекурсий

Хорошая рекурсия (факториал):

def factorial(n):
    if n <= 1:  # Базовый случай
        return 1
    return n * factorial(n - 1)  # Рекурсивный случай

print(factorial(100))  # Работает отлично

Плохая рекурсия (Фибоначчи без оптимизации):

def fib_bad(n):
    if n <= 1:
        return n
    return fib_bad(n - 1) + fib_bad(n - 2)

try:
    print(fib_bad(1000))
except RecursionError:
    print("Слишком глубокая рекурсия!")

4. Решение: мемоизация (Memoization)

Кэшируем результаты уже вычисленных значений:

from functools import lru_cache

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

print(fib_good(1000))  # Работает за O(n)

5. Решение: итеративный подход (лучший вариант)

Переведите рекурсию в цикл:

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

print(factorial_iterative(1000))  # Никаких проблем

Для Фибоначчи:

def fib_iterative(n):
    if n <= 1:
        return n
    
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

print(fib_iterative(1000))  # O(n), O(1) памяти

6. Использование стека для имитации рекурсии

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            stack.extend(graph[node])
    
    return visited

7. Увеличение лимита (осторожно!)

import sys

old_limit = sys.getrecursionlimit()
sys.setrecursionlimit(10000)

try:
    result = expensive_recursion()
finally:
    sys.setrecursionlimit(old_limit)

Риски: может привести к crash приложения, всё равно исчерпается память. Лучше рефакторить, чем увеличивать.

Итоговые рекомендации

• Глубина рекурсии в Python — максимум 1000 уровней (по умолчанию)
• Для больших глубин переходите на итеративный подход
• Используйте мемоизацию для оптимизации рекурсивных алгоритмов
• Избегайте наивной рекурсии без кэширования
• Увеличивайте лимит только в крайних случаях

В production коде предпочитайте итеративные решения — они более надёжны и предсказуемы.