What Is the Maximum Recursion Depth in Python, and How to Increase It

What is the maximum recursion depth in Python, and how to increase it?

It is a guard against a stack overflow, yes. Python (or rather, the CPython implementation) doesn't optimize tail recursion, and unbridled recursion causes stack overflows. You can check the recursion limit with sys.getrecursionlimit:

import sys
print(sys.getrecursionlimit())

and change the recursion limit with sys.setrecursionlimit:

sys.setrecursionlimit(1500)

but doing so is dangerous -- the standard limit is a little conservative, but Python stackframes can be quite big.

Python isn't a functional language and tail recursion is not a particularly efficient technique. Rewriting the algorithm iteratively, if possible, is generally a better idea.

How could you increase the maximum recursion depth in Python?

import sys

sys.setrecursionlimit(2000)

increasing recursion depth in python to 100000

The problem comes from your merge(left, right) implementation which is recursive in O(n). You merge two sorted list by one element at each recursion step. The idea of merge being recursive may make sense in languages where tail-recursion is optimized, but it is not the case in python.

In general, merge is iterative as its complexity will always be at least the number of elements to merge.

def merge(left, right):
    merged = []
    i = 0
    j = 0
    while i < len(left) and j < len(right) :
        if left[i] < right[j]:
            merged.append(left[i])
            i+=1
        else:
            merged.append(right[j])
            j+=1
    merged += left[i:]
    merged += right[j:]
    return merged

RecursionError: maximum recursion depth exceeded in comparison

When a RecursionError is raised, the python interpreter may also offer you the context of the call that caused the error. This only serves for debugging, to give you a hint where in your code you should look in order to fix the problem.

See for example this circular str-call setup that leads to a different message:

>>> class A:
...     def __str__(self):
...         return str(self.parent)
>>> a = A()
>>> a.parent = a
>>> str(a)
RecursionError: maximum recursion depth exceeded while calling a Python object

---

There is no documentation of this behaviour on the issue discussion where RecursionError was introduced, but you can just search the cpython code for occurences of Py_EnterRecursiveCall. Then you can see the actual contexts that will be returned depending on where the error is raised:

Py_EnterRecursiveCall(" while encoding a JSON object")
Py_EnterRecursiveCall(" while pickling an object")
Py_EnterRecursiveCall(" in __instancecheck__")
Py_EnterRecursiveCall(" in __subclasscheck__")
Py_EnterRecursiveCall(" in comparison")
Py_EnterRecursiveCall(" while getting the repr of an object")
Py_EnterRecursiveCall(" while getting the str of an object")
Py_EnterRecursiveCall(" while calling a Python object")
Py_EnterRecursiveCall("while processing _as_parameter_") # sic
# .. and some more that I might have missed

Why is the maximum recursion depth in python 1000?

Here is a better test:

n = 0

def test_recursion_limit():
    def call():
        global n
        n += 1
        call()
    try:
        call()
    except RuntimeError:
        print(n)

test_recursion_limit()

If you put it in spam.py and execute that, it should return 998 for both python2 and python3. It's one stack frame short because of the initial test_recursion_limit frame.

If you're running in a REPL such as ipython, you are already inside a few frames, so you will see a lower count - it's not that the recursion limit is undershot, it's that the implementation of the REPL itself uses some stack frames.

>>> # freshly opened ipython session
>>> import inspect
>>> len(inspect.stack())
10

You can check the current recursion limit by calling sys.getrecursionlimit() function. The default value of 1000 is chosen as a sensible default, it's a safeguard against eclipsing system resources when you accidentally execute an infinitely recursive call. That's very easy to do when mucking around with custom __getattr__ implementations, for example.

If you're blowing the stack legitimately and you need to increase the limit, it can be modified with sys.setrecursionlimit.

Why does increasing the recursion depth result in stack overflow error?

The recursion limit was successfully updated, since the first errors message was:

RecursionError: maximum recursion depth exceeded

and then after increasing the recursion depth, the error message changed to:

MemoryError: Stack overflow

From the documentation on sys.setrecursionlimit():

Set the maximum depth of the Python interpreter stack to limit. This limit prevents infinite recursion from causing an overflow of the C stack and crashing Python.

Hence, by increasing the recursion limit, the program crashed the Python interpreter.

Since Python does not optimize tail recursion, unlimited recursion causes the stack to overflow (run out of memory).

In many real-world applications it is necessary to implement functions without recursion to avoid stack overflow memory errors.

See also: Setting stacksize in a python script

Maximum recursion depth exceeded in comparison in python turtle

This is due to an indentation error:

if n>=1:
    forward(n)
    left(60)
hexagon(n-1)

Which should be:

if n>=1:
    forward(n)
    left(60)
    hexagon(n-1)

And similarly in the square() function. The complete code:

from turtle import *

def hexagon(n):
    if n >= 1:
        forward(n)
        left(60)
        hexagon(n-1)

def square(n):
    if n >= 1:
        forward(n*5)
        right(90)
        square(n-1)

hexagon(100)
clearscreen()
square(50)

done()

---

Related Topics