Python: Maximum Recursion Depth Exceeded

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.

RecursionError: maximum recursion depth exceeded while calling a Python object. python error

if the_list is of length 1 (which will happen at some stage in your recursive calls) you will end up in an infinite recursion... (mid will be 0).

you need to address that as well as a base case:

def sum_list(the_list):
    if not the_list:
        return 0
    if len(the_list) == 1:
        return the_list[0]
    else:
        mid = len(the_list) // 2
        return sum_list(the_list[:mid]) + sum_list(the_list[mid:])

i assume this is an exercise in recursion. python offers sum to do that efficiently.

Databricks Exception: ERROR: maximum recursion depth exceeded in comparison

Error - Exception: ERROR: maximum recursion depth exceeded in
comparison

This error is related to Recursion Depth Limit in Python.

This error says it all—maximum recursion depth exceeded in comparison. This tells you that Python’s recursion depth limit of 1000 is reached.

A recursive function could call itself indefinitely. In other words, you could end up with an endless loop.

Also, a stack overflow error can occur even if the recursion is not infinite. This can happen due to too big of a stack frame.

In Python, the recursion depth limit takes these risks out of the equation.
Python uses a maximum recursion depth of 1000 to ensure no stack overflow errors and infinite recursions are possible.

This recursion limit is somewhat conservative, but it is reasonable as stack frames can become big in Python.

How to Change the Recursion Depth Limit in Python

import sys
print(sys.setrecursionlimit(2000))

For more information follow this article by Artturi Jalli

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

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.

Maximum recursion depth exceeded when finding the depth of binary-search-tree

The recursion depth should not be that great on the condition that your binary tree is relatively balanced. Still, even when your binary tree is degenerate, like is what happens when you create it from a sorted sequence (sorted) then you should still only need O(n) stack space.

But your code for both bst_build and find_depth needs a lot more stack space. This is because they don't backtrack when reaching a leaf. Instead they both restart a traversal from the root, without getting out of the current recursion tree first:

• bst_build does this by calling bst_build again when it wants to insert the next input from seq. This should happen in a loop (outside of recursion), not when you are already deep in a recursion tree.
• find_depth does this by calling find_depth again when it reaches a leaf. This should happen by first backtracking one step and then recurring again into a sibling node. Instead it restarts the search from the root (which is a waste of time), and does so without getting out of recursion first.

This makes this code need a tremendous amount of stack space, which will be like O(n²) in the worst (degenerate) case.

Not related to your question, but it is a pity -- and completely unnecessary -- that find_depth destroys the tree as it is being traversed.

Another problem that is not related to your question: your bst_check is not correct. It will return True for the following tree:

            2
           /
          1
           \
            3

Yet, this tree is not a valid BST. The requirement for a valid BST is not only that a left child is less than its parent, but that all nodes in the left subtree are less than that parent.

Here is a fix for all these issues:

def bst_build(seq):
    if not seq:
        return None

    def add_child(main, value):
        if value == main[0]:
            return
        childindex = 1 if main[0] > value else 2
        if not main[childindex]:
            main[childindex] = [value, None, None]
        else:
            add_child(main[childindex], value)

    binary_search_tree = [seq[0], None, None]
    for value in seq[1:]:
        add_child(binary_search_tree, value)

    return binary_search_tree

def bst_depth(b):
    return 1 + max(bst_depth(b[1]) if b[1] else -1, bst_depth(b[2]) if b[2] else -1)

def bst_check(b, low=float("-inf"), high=float("inf")):
    return not b or (low <= b[0] <= high and bst_check(b[1], low, b[0]) 
                                         and bst_check(b[2], b[0], high))

Segmentation fault: 11 / RecursionError: maximum recursion depth exceeded while calling a Python object

Method 1

The issue lies in the recursive calls:

    elif target < l[midpoint]:
        return binary_search(l, target,low = None, high = midpoint - 1) 
    else:
        # target > l[midpoint]
        return binary_search(l, target, low = midpoint + 1, high = None)

You want to copy the low, and high rather than setting them to None. The correct call should be:

    elif target < l[midpoint]:
        return binary_search(l, target,low = low, high = midpoint - 1) 
    else:
        # target > l[midpoint]
        return binary_search(l, target, low = midpoint + 1, high = high)

---

To demonstrate the bug:

Using your example, in the original call: low=0, high=8

Then, in the 1st recursion, low=0, high=4.

Now, target=10 > midpoint=5, you code makes the following call

binary_search(l, target, low = midpoint + 1, high = None)

Since high=None, it will be set to high=8 in the next recursion, giving you low=3, high=8. This is not what you want, since you already eliminated the top half. So you need to carry over low and high in the recursive call rather than setting them to None.

To be more efficient, you can also check l[low] and l[high] in addition to l[midpoint] against the target.

---

Method 2

Alternatively, you can give a subset of the list in the recursive call. Then, you don't really need the low and high argument any more. Since slicing only generate new references rather than copies, it doesn't have too much impact on memory.

    elif target < l[midpoint]:
        return binary_search(l[low:midpoint], target,low = None, high = None) 
    else:
        # target > l[midpoint]
        return binary_search(l[midpoint+1:high+1], target, low = None, high = None)

---

Related Topics