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

I have this tail recursive function here:

def recursive_function(n, sum):
    if n < 1:
        return sum
    else:
        return recursive_function(n-1, sum+n)

c = 998
print(recursive_function(c, 0))

It works up to n=997, then it just breaks and spits out a RecursionError: maximum recursion depth exceeded in comparison. Is this just a stack overflow? Is there a way to get around 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.

Looks like you just need to set a higher recursion depth:

import sys
sys.setrecursionlimit(1500)

It's to avoid a stack overflow. The Python interpreter limits the depths of recursion to help you avoid infinite recursions, resulting in stack overflows. Try increasing the recursion limit (sys.setrecursionlimit) or re-writing your code without recursion.

From the Python documentation:

sys.getrecursionlimit()

Return the current value of the recursion limit, the maximum depth of the Python interpreter stack. This limit prevents infinite recursion from causing an overflow of the C stack and crashing Python. It can be set by setrecursionlimit().

If you often need to change the recursion limit (e.g. while solving programming puzzles) you can define a simple context manager like this:

import sys

class recursionlimit:
    def __init__(self, limit):
        self.limit = limit

    def __enter__(self):
        self.old_limit = sys.getrecursionlimit()
        sys.setrecursionlimit(self.limit)

    def __exit__(self, type, value, tb):
        sys.setrecursionlimit(self.old_limit)

Then to call a function with a custom limit you can do:

with recursionlimit(1500):
    print(fib(1000, 0))

On exit from the body of the with statement the recursion limit will be restored to the default value.

P.S. You may also want to increase the stack size of the Python process for big values of the recursion limit. That can be done via the ulimit shell builtin or limits.conf(5) file, for example.

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

Related

Recent Posts