Python: Каков жесткий предел рекурсии для Linux, Mac и Windows?

Question

Модуль Python sys предоставляет функцию setrecursionlimit, которая позволяет изменять максимальный предел рекурсии Python. Документы говорят:

Максимально возможный предел зависит от платформы.

Мой вопрос: каковы максимальные пределы для различных платформ в CPython? Я хотел бы знать значения для Linux, Mac и Windows.

ОБНОВЛЕНИЕ: Можем ли мы избежать ответов "Вы делаете это неправильно"? Я знаю, что попытка сделать очень глубокую рекурсию, как правило, плохая идея. Я рассмотрел плюсы и минусы в своей конкретной ситуации и решил, что хочу это сделать.

Answer 1

В Windows (по крайней мере), sys.setrecursionlimit не полная история. Жесткий лимит устанавливается для каждого потока, и вам нужно вызвать threading.stack_size и создать новый поток, как только вы достигнете определенного предела. (Я думаю, что 1 МБ, но не уверен) Я использовал этот подход, чтобы увеличить его до стека 64 МБ.

import sys
import threading

threading.stack_size(67108864) # 64MB stack
sys.setrecursionlimit(2 ** 20) # something real big
                               # you actually hit the 64MB limit first
                               # going by other answers, could just use 2**32-1

# only new threads get the redefined stack size
thread = threading.Thread(target=main)
thread.start()

Я не пытался понять, какие ограничения могут быть на threading.stack_size, но не стесняйтесь попробовать ... вот где вам нужно посмотреть.

Таким образом, sys.setrecursionlimit - это просто ограничение, установленное самим интерпретатором. threading.stack_size позволяет манипулировать фактическим лимитом, установленным ОС. Если вы превысите последний предел первым, Python просто полностью рухнет.

Answer 2

Значения по умолчанию для основных операционных систем;

• Для Windows: 2000
• Для Linux: 1000
• Для Mac OS: 1000

Answer 3

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

В CPython рекурсия хороша для обхода структур данных (где ограничение 1000 должно быть достаточно для всех), но не для алгоритмов. Если бы я должен был реализовать, скажем, алгоритмы, связанные с графами, и достичь предела рекурсии, я бы либо реализовал свой собственный стек и использовал итерации, либо искал библиотеки, реализованные на C / C ++ / что угодно, прежде чем поднимать предел вручную.