Handling Recursion Limit in Python

In this tutorial, we will learn to handle recursion limit in Python.

Programming languages such as C or C++ perform tail recursion optimization. Python interpreter does not have any such property. Because of this, Python sets a very small number as the recursion limit which is generally of order 10^4. Therefore, if we have a recursive function in Python, it will throw an error for large input to avoid any stack overflow.

Have a look at the given code and the output below.

def rec_fun(n):
    if n == 0:
        return 0
    
    return rec_fun(n-1) + n
    
n = 1000
print(rec_fun(n))

Output:

Traceback (most recent call last):
File "err.py", line 8, in <module>
print(rec_fun(n))
File "err.py", line 5, in rec_fun
return rec_fun(n-1) + n
File "err.py", line 5, in rec_fun
return rec_fun(n-1) + n
File "err.py", line 5, in rec_fun
return rec_fun(n-1) + n
[Previous line repeated 994 more times]
File "err.py", line 2, in rec_fun
if n == 0:
RecursionError: maximum recursion depth exceeded in comparison

The rec_fun in the above program is a recursive function that returns the sum of all natural numbers from 1 to n. As you can see, when we set the value of n to 1000, an error is thrown because the recursion limit is reached.

How to change the recursion limit

Python has a setrecursionlimit() method that helps us manipulate the recursion limit for a recursive function. This method is present in sys module in Python. It takes one parameter as the new recursion limit. The below program demonstrates the working of this method. See the code.

import sys

def rec_fun(n):
    if n == 0:
        return 0
    
    return rec_fun(n-1) + n
    
sys.setrecursionlimit(10**6)

n = 1000
print(rec_fun(n))

Output:

500500

As you can see, the program now works for the input given in the first example program as we have increased the recursion limit.

Thank you.

Also read: Finding the power of a number using recursion in Python

Leave a Reply

Your email address will not be published. Required fields are marked *