🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
🤔 Какие ограничения есть у рекурсии в Python?
Рекурсия — это мощный инструмент, но в Python она имеет ограничения, которые нужно учитывать при написании кода.
🟠Ограничение на глубину рекурсии (`sys.getrecursionlimit()`)
В Python по умолчанию рекурсия ограничена 1000 вызовами, чтобы избежать переполнения стека.
import sys
print(sys.getrecursionlimit()) # 1000 (обычное значение)
Если превысить этот лимит, программа вызовет ошибку
def recursive():
return recursive()
recursive() # RecursionError: maximum recursion depth exceeded
🚩Как изменить лимит?
Можно увеличить глубину рекурсии, но это небезопасно
sys.setrecursionlimit(2000) # Увеличиваем до 2000
🟠Рекурсия требует много памяти
Каждый рекурсивный вызов создаёт новый фрейм в стеке вызовов.
def factorial(n):
if n == 1:
return 1
return n * factorial(n - 1)
print(factorial(10000)) # Ошибка из-за переполнения стека
🟠Отсутствие оптимизации хвостовой рекурсии
Другие языки (например, Lisp, JavaScript) автоматически оптимизируют хвостовую рекурсию (Tail Call Optimization, TCO).
Python не делает этого, поэтому даже "идеальная" рекурсия всё равно переполняет стек.
def tail_recursive(n, acc=1):
if n == 1:
return acc
return tail_recursive(n - 1, n * acc)
print(tail_recursive(1000)) # Всё равно вызовет RecursionError
🟠Рекурсия медленнее цикла
Рекурсивный вызов требует больше накладных расходов (создание стек-фреймов), чем обычный for или while.
# Итеративный вариант (быстрее)
def factorial_iter(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
# Рекурсивный вариант (медленнее)
def factorial_rec(n):
if n == 1:
return 1
return n * factorial_rec(n - 1)
Ставь 👍 и забирай 📚 Базу знаний