Почему предел максимальной глубины рекурсии в Python 2 ** 32/2 - 31?
В Python некоторые программы создают ошибку RecursionError: maximum recursion depth exceeded in comparison или что-то подобное.
Это связано с тем, что существует ограничение на глубину вложенности рекурсии.
Чтобы получить текущее значение максимальной глубины рекурсии, используйте
import sys
sys.getrecursionlimit()
Значение по умолчанию составляет 1000 или 1500 в зависимости от конкретной комбинации system/python/....
Значение можно увеличить, чтобы получить доступ к более глубокой рекурсии.
import sys
sys.setrecursionlimit(LIMIT)
где LIMIT — новый предел.
Это ошибка, которую я получаю, когда превышаю предел «предела»:
OverflowError: Python int too large to convert to C int
Почему «лимит» лимит int(2**32 / 2) - 31?
Я ожидаю, что это может быть int(2**32 / 2) - 1, поскольку целые числа являются знаковыми (32-битными) числами, но почему - 31?
Впервые этот вопрос возник, когда я тестировал версию 3.9.13 (64-разрядную версию). Я также тестировал версию 3.12 (64-разрядную версию).
Обновлено: Вот демо-версия IDLE с Python 3.9.13.
Python 3.9.13 (tags/v3.9.13:6de2ca5, May 17 2022, 16:36:42) [MSC v.1929 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license()" for more information.
>>> import sys
>>> v = 2**31-1
>>> print(v)
2147483647
>>> sys.setrecursionlimit(v)
Traceback (most recent call last):
File "<pyshell#3>", line 1, in <module>
sys.setrecursionlimit(v)
OverflowError: Python int too large to convert to C int
>>> v = 2**31-30
>>> sys.setrecursionlimit(v)
Traceback (most recent call last):
File "<pyshell#5>", line 1, in <module>
sys.setrecursionlimit(v)
OverflowError: Python int too large to convert to C int
>>> v = 2**31-31
>>> sys.setrecursionlimit(v)
>>>
Это (2**32)/2 - 1, то есть 2**31 - 1, то есть максимальное значение для целого числа C со знаком. Не знаю, откуда у вас -31. Вы хотите сказать, что Python в вашей системе будет жаловаться, если вы установите предел выше 2**31 - 31? У меня нет: i.sstatic.net/keSR2Ub8.png
Вы читали документацию? «Максимально возможный предел зависит от платформы».
Не говоря уже о том, что int(x / y) эквивалентно x // y для положительных чисел (или, по крайней мере, положительных целых чисел в этом диапазоне).
С другой стороны: из-за накладных расходов на вызов функций Python и того, как среда выполнения распределяет использование памяти, имейте в виду, что ваш истинный предел рекурсии будет намного ниже этого. Возможно, вы сможете достичь 100_000 без сбоя во время выполнения, но я бы не стал на это делать ставку.
(хорошо - в более новой версии Python я без проблем заставил его работать с 10_миллионами рекурсивных вызовов. 100_миллион дал мне OOM - со старым (до 3.12) около 10_000 приводило к сбою среды выполнения)
@jsbueno Да, чистая рекурсия Python теперь ограничена объемом вашей памяти, а не размером вашего стека C. Вы можете совершить более 10_000_000 вызовов на ГБ, если они экономны: Попробуйте это онлайн!
Я использовал этот ответ для своего теста. До сих пор я запускал лимит-тест только на 3.12. Сейчас я еще и на нем протестировал функцию (ackermann) и вроде обе версии тоже ведут себя по-разному. Кажется, что в 3.9.13 используются все ~2 миллиарда и на самом деле заканчивается довольно быстро (без решения). На 3.12 работает дольше, чем хотелось бы дождаться короткого теста. Возможно, имелось в виду что-то вроде @jhole, но я НЕ использую LRU-кэш. В обеих версиях используется незначительное количество оперативной памяти.
Ответы 1
Обычно предельным «пределом» будет 2**31 - 1, то есть максимальное значение для целого числа C со знаком (хотя максимально возможный предел документирован как зависящий от платформы).
Более низкий полезный диапазон, который вы получаете в IDLE, объясняется тем, что он оборачивает встроенную функцию для наложения нижнего предела:
>>> import sys
>>> sys.setrecursionlimit
<function setrecursionlimit at 0xcafef00d>
>>> sys.setrecursionlimit.__wrapped__
<built-in function setrecursionlimit>
Это специфично для IDLE, и в противном случае вы должны увидеть «полную» 2**31-1 глубину при использовании того же интерпретатора на той же платформе.
Вы можете найти обезьяний патч здесь, в исходниках CPython: Lib/idlelib/run.py:install_recursionlimit_wrappers
Используемые значения уменьшаются на RECURSIONLIMIT_DELTA=30 , а комментарий к ссылкам на функции-оболочки bpo-26806 (IDLE не отображает трассировки и зависания RecursionError), где Терри Дж. Риди упоминает причину исправления нижнего предела:
IDLE добавляет собственные вызовы в стек вызовов до (и, возможно, после) запуска пользовательского кода.
Вы также должны увидеть это в строке документации:
Здесь остался без ответа один вопрос: почему вообще требуется C int. Python реализован на языке C, так что, возможно, это неудивительно.
help(sys.setrecursionlimit) тоже подойдет, правда?
@nocomment, верно.
@MarkRansom Да - github.com/python/cpython/blob/v3.12.4/Python/ceval.c#L235-L252
Из любопытства я проверил, что здесь делает PyPy, поскольку у них нет реальной причины использовать C int. На PyPy вас молча ограничивают до 1 миллиона! github.com/pypy/pypy/blob/…
Другой вопрос, почему он не использует беззнаковый вместо знаковый.
Тем более, что разрешены только числа >= 1.
вас может заинтересовать github.com/python/cpython/issues/112282