Adjusting recursion limit in Python (overcoming RecursionError)

I was recently solving some algorithmic puzzle in Python and faced a RecursionError when coding my solution in a recursive fasion. Here's a quick tip how it can be fixed.

TL;DR: Check your current recursion limit with sys.getrecursionlimit() and adjust it to your program needs with sys.setrecursionlimit(level) (maximum supported level varies by the platform you're using). Be cautious as it might lead to crashing your program + hitting RecursionError might indicate a bigger flaw in your code (is recursion the best approach?).

Warning

Changing default recursion limit is a hack.

Facing RecursionError could be an indicator for you that your approach is suboptimal and the problem you're trying to solve can be handled in a better way (by switching to other approach - for example iterative one).

There's also a performance penalty - Python does not support tail call optimization and every function call results in a new frame being added to the call stack (which is expensive).

Having said that, if you'd like to see you can change recursion limit with a short example, please continue.

Exemplary recursive function

Let's define a simple recursive function that is equivalent of Python's built-in sum() - it accepts an iterable of numbers and returns their sum (but calculates it using recursion):

from typing import Iterable


def recursive_sum(nums: Iterable) -> int:
    if not nums:
        return 0
    head, *tail = nums
    return head + recursive_sum(tail)

Let's test if it works:

assert recursive_sum([1, 5]) == 6
assert recursive_sum(range(5)) == 10

Looks good :-)!

Explore its current limits

Let's try to calculate sums of first n numbers from 0 to n (n excluded). We can easily define such number sequence in Python with range(n).

For 1000:

>>> recursive_sum(range(1000))
499500

For 2000:

>>> recursive_sum(range(2000))
1999000

For 3000:

>>> recursive_sum(range(3000))
...
RecursionError: maximum recursion depth exceeded while calling a Python object

Looks like calcuating sum for first 3000 numbers is not possible on my computer while using default settings (note that it might happen earlier/later on your system since default recursion limit might vary between our systems).

sys module for the rescue!

sys module exposes two helpful functions for such case - sys.getrecursionlimit() and sys.setrecursionlimit(limit).

Citing official 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().

sys.setrecursionlimit(limit)

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.

The highest possible limit is platform-dependent. A user may need to set the limit higher when they have a program that requires deep recursion and a platform that supports a higher limit. This should be done with care, because a too-high limit can lead to a crash.

If the new limit is too low at the current recursion depth, a RecursionError exception is raised.

Changed in version 3.5.1: A RecursionError exception is now raised if the new limit is too low at the current recursion depth.

Having above knowledge, let's find out what is recursion limit set by default on my system:

>>> import sys
>>> sys.getrecursionlimit()
3000

Test if bumping it to 5000 will make recursive_sum(range(3000)) work:

>>> sys.setrecursionlimit(5000)
>>> recursive_sum(3000)
4498500

Voilà - our recursive function now works :-)!

Closing remarks

Hope that you find this useful. As mentioned in the docs for sys.setrecursionlimit(limit) - be aware that increasing recursion limit too much might lead to stack overflow and crashing your program + see warning part at the beginning of the article.

Happy recursing and all the best in 2022,
Kuba

Thanks for reading the article, I really appreciate it! Have you heard about Braintrust - the first decentralized talent network? Whether you're a freelancer looking for a job, an employer looking for hiring talents, or you just have a wide network of connections - there's something for you there!

Go check it out and register with below link (yeah - it's my referral link and it's free - no hidden costs):

Registration link