How to Set The Maximum Recursion Depth In

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)

Set maximum recursion depth in java

Create this class:

public class RecursionLimiter {
    public static int maxLevel = 10;

    public static void emerge() {
        if (maxLevel == 0)
            return;
        try {
            throw new IllegalStateException("Too deep, emerging");
        } catch (IllegalStateException e) {
            if (e.getStackTrace().length > maxLevel + 1)
                throw e;
        }
    }
}

Then import static and insert emerge() call into the beginning of any method in your code that can be deeply recursive. You can adjust maximum allowed recursion level via the maxLevel variable. The emerge() procedure will interrupt execution on a level greater than the value of that variable. You can switch off this behaviour by setting maxLevel to 0. This solution is thread-safe because it doesn't use any counter at all.

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

How do you set the maximum recursion depth in?

Ah. Found it by reading the error message. This will set the recursion depth to 100000

> options(expressions= 100000)

What is the recursion depth and why is set to a fixed limit?

A function is recursive if it calls itself either directly or via some other function that it calls. While recursion is a useful way to build an algorithm it can be a resource hog. Each time the function is called, it creates some local state (the local variables) and memory space remains in use until the function finally returns. If your recursive calls go a million deep, that's a million local frames in memory.

The risk is that recursion will blow up the stack frame or process memory and you will get a hard failure of the code. This is a really bad error as the entire program exits with no ability to clean up. Even if the program doesn't crash, it uses a lot of memory, impacting the rest of your system. There could be more swapping and worse case, the Linux oom killer could randomly kill processes in an attempt to get resources for the kernel.

To mitigate risk from either accidental recursion or a buggy algorithm that doesn't properly limit itself, python puts a limit on recursion. But developers can override that limit via sys.setrecursionlimit(some_huge_number) in which case anything bad is on their heads.

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))

---

Related Topics