Question

Why is the 'limit' limit of maximum recursion depth in python 2**32 / 2 - 31?

In Python, some programs create the error RecursionError: maximum recursion depth exceeded in comparison or similar.

This is because there is a limit set for how deep the recursion can be nested.

To get the current value for maximum recursion depth, use

import sys
sys.getrecursionlimit()

The default value seems to be 1000 or 1500 depending on the specific system/python/... combination.

The value can be increased to have access to deeper recursion.

import sys
sys.setrecursionlimit(LIMIT)

where LIMIT is the new limit.

This is the error that I get when I exceed the 'limit' limit:

OverflowError: Python int too large to convert to C int

Why is the 'limit' limit int(2**32 / 2) - 31?

I would expect that it maybe is int(2**32 / 2) - 1 as it makes sense that integers are signed (32-bit) numbers, but why - 31?

The question first came up as I was testing with 3.9.13 (64-bit). I also tested with 3.12 (64-bit).

Edit: Here is a demo on IDLE with 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  95  2
1 Jan 1970

Solution

 4

Usually the limit "limit" would be 2**31 - 1, i.e. the max value for a signed C integer (although the highest possible limit is documented as being platform-dependent).

The lower usable range you get within IDLE is because it wraps the built-in function to impose a lower limit:

>>> import sys
>>> sys.setrecursionlimit
<function setrecursionlimit at 0xcafef00d>
>>> sys.setrecursionlimit.__wrapped__
<built-in function setrecursionlimit>

This is specific to IDLE, and you should see the "full" 2**31-1 depth when using the same interpreter on the same platform otherwise.

You can find the monkeypatch here in CPython sources: Lib/idlelib/run.py:install_recursionlimit_wrappers

Usable values are reduced by RECURSIONLIMIT_DELTA=30, and a comment on wrapper function references bpo-26806 (IDLE not displaying RecursionError tracebacks and hangs), where Terry J. Reedy mentions the reason for patching a lower limit:

IDLE adds it own calls to the call stack before (and possibly after) running user code

You should also see that in the docstring:

idle docstring

2024-07-19
wim