Лимит 1000 — почему именно столько
Python устанавливает sys.getrecursionlimit() == 1000 по умолчанию. Это число выбрано как компромисс:
- Достаточно высоко для большинства практических рекурсий (log(n) на огромных данных — около 30-40).
- Достаточно низко, чтобы предотвратить segfault на стандартном OS-стеке 8 МБ при средних frames CPython.
Лимит проверяется в C-функции _Py_CheckRecursiveCall на каждый CALL_FUNCTION. При превышении бросается RecursionError. Это не настоящий stack overflow ОС, это защита Python ДО реального переполнения.
import sys
print(sys.getrecursionlimit()) # 1000 (по умолчанию)
def count(n):
if n == 0:
return 0
return 1 + count(n - 1)
count(990) # ok
count(1000) # RecursionError: maximum recursion depth exceededКонкретное число «1000 vs 990» зависит от: глубины стека к моменту вызова (если main позвал hands main позвал hands), количества скрытых frames (вызовы внутри генераторов, контекст-менеджеров).
sys.setrecursionlimit — когда безопасно
Поднять лимит можно:
import sys
sys.setrecursionlimit(10_000)Безопасно ли это? Зависит от того, насколько вы близки к реальному пределу OS-стека.
Расчёт. OS-stack обычно 8 МБ (Linux/macOS, main thread). Один CPython frame ~500 байт. Максимально безопасная глубина: 8 МБ / 500 байт = ~16 000 frames. С запасом 50% — 8000-10000.
sys.setrecursionlimit(10_000) # вероятно безопасно
sys.setrecursionlimit(1_000_000) # почти наверняка segfaultС 1_000_000 Python не выдаст RecursionError, потому что искусственный лимит не превышен. Но OS-стек переполнится — процесс умрёт с segmentation fault без шанса обработать исключение.
sys.setrecursionlimit(10**6) — антипаттерн. Если у вас глубокая рекурсия, проблема не в лимите Python, а в выборе алгоритма. Переписывайте на итерацию.
Изменение в потоках (threading)
Если рекурсия в Python-thread, OS-стек обычно меньше: 1 МБ по умолчанию. Соответствующий лимит — около 2000 frames.
Поэтому есть классический баг: «работает в main, падает в потоке с тем же кодом». Решение — задать размер стека до создания потока:
import threading
threading.stack_size(8 * 1024 * 1024) # 8 МБ
def worker():
deep_recursion(5000) # теперь ok
t = threading.Thread(target=worker)
t.start()Заметьте: stack_size() влияет только на потоки, создаваемые после вызова, и только на новые. Main-thread имеет размер, заданный ОС, изменить его сложнее.
Как переписать рекурсию через явный стек
Любая рекурсия эквивалентна циклу с явным стеком. Главная идея: вместо использования call stack ОС, мы держим стек состояний в обычном Python list.
# рекурсивный DFS дерева
def dfs_recursive(node):
if node is None:
return
print(node.value)
dfs_recursive(node.left)
dfs_recursive(node.right)
# итеративный с явным стеком
def dfs_iterative(root):
if root is None:
return
stack = [root]
while stack:
node = stack.pop()
print(node.value)
# push в обратном порядке: правый первый, чтобы левый вышел первым
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)Разница: рекурсивный код использует call stack ОС, итеративный — Python list в heap. Heap может расти до миллиардов элементов (упирается только в RAM), стек — нет.
Итеративная версия не падает на глубоких деревьях. Это главная причина переписывать рекурсию в DFS, parsing и подобных задачах для production.
Шаблон преобразования
Универсальный шаблон, превращающий рекурсию в итерацию:
def recursive(state):
if base(state):
return base_value
sub = recursive(transform(state))
return combine(state, sub)
# превращается в
def iterative(initial_state):
stack = [(initial_state, False)] # (state, processed_subcall?)
result_stack = []
while stack:
state, processed = stack.pop()
if base(state):
result_stack.append(base_value(state))
elif not processed:
# сначала надо обработать подзадачу
stack.append((state, True)) # потом мы вернёмся к combine
stack.append((transform(state), False)) # сначала обработать sub
else:
# подзадача обработана, её результат сверху result_stack
sub = result_stack.pop()
result_stack.append(combine(state, sub))
return result_stack[0]Это сложнее, чем рекурсия — потому что мы вручную моделируем то, что компилятор делает автоматически. Но это работает на любой глубине.
На практике, если рекурсия простая (один tail call) — переписывайте в while. Если ветвистая — используйте описанный шаблон.
Tail recursion в Python 3.13
В Python 3.13 (релиз 2024) появилась специфическая оптимизация — computed gotos в интерпретаторе и некоторые tail calls на C-уровне. Это даёт 10-15% общего ускорения для bytecode-интенсивного кода.
Важно: это не TCO для Python-функций. Ваши def f(...): return f(...) всё равно создают новый frame и упираются в setrecursionlimit. Изменения коснулись только того, как C-интерпретатор переключается между bytecode-инструкциями.
Гвидо неоднократно подтверждал: TCO для Python-уровня не планируется. Если ваш алгоритм требует tail-рекурсию глубиной миллион — пишите цикл.
Замеры — что реально безопасно
Эксперимент: какая максимальная глубина рекурсии работает на вашей машине?
import sys
def find_max_depth():
sys.setrecursionlimit(100_000) # высокий лимит Python
def deep(n):
if n == 0:
return 0
return 1 + deep(n - 1)
lo, hi = 1, 100_000
while lo < hi:
mid = (lo + hi + 1) // 2
try:
deep(mid)
lo = mid
except RecursionError:
hi = mid - 1
return lo
# можно упасть segfault'ом! раскомментируйте на свой риск
# print(f"max safe depth: {find_max_depth()}")На моей машине (macOS, Python 3.13, 8 МБ stack) — около 14 000-20 000 frames до RecursionError. Если поднять лимит ещё выше — попадёшь в реальный OS stack overflow, segfault.
Решения по приоритету: проблему рекурсии решить, не лимит увеличивать.
Реальные сценарии «нужна глубокая рекурсия»
-
Парсинг глубоко вложенного JSON. Файл с массивом массивов массивов на 5000 уровней. JSON-парсер на рекурсии падает. Решение — итеративный парсер (как в
jsonмодуле — он на C, без проблем). -
DFS большого графа. Дерево или граф с цепочками длиной 10000+. Решение — переписать на итеративный DFS с явным стеком.
-
Регулярные выражения с глубоким backtracking. Pathological regex может уйти в глубокий backtracking и падать. Решение — переписать regex (атомарные группы, possessive quantifiers).
-
Парсер выражений (calculator). Скобки на 5000 уровней. Решение — Pratt parser или Shunting-yard алгоритм, итеративные оба.
В каждом случае правильное решение — алгоритмическое, а не «увеличить setrecursionlimit».
Попробуй сам
Дано бинарное дерево. Сделайте рекурсивный sum_tree (сумма всех узлов) и итеративный с явным стеком. Сравните, что работает на дереве с цепочкой длиной 5000.
import sys
sys.setrecursionlimit(2000)
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
# построим вырожденное дерево-цепочку
root = Node(1)
cur = root
for i in range(2, 5001):
cur.left = Node(i)
cur = cur.left
# рекурсивный — упадёт
def sum_recursive(node):
if node is None:
return 0
return node.val + sum_recursive(node.left) + sum_recursive(node.right)
# итеративный — работает
def sum_iterative(root):
if root is None:
return 0
total = 0
stack = [root]
while stack:
node = stack.pop()
total += node.val
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return total
try:
print(sum_recursive(root))
except RecursionError:
print("recursive failed: too deep")
print(sum_iterative(root)) # 12502500, ok