What Is The Recursion Limit?

A recursive function is one that calls itself, looping through data to generate a result. However, in Python, there is a limit to the number of times a function can call itself. The limit is set to the maximum depth of Python’s interpreter stack. 

Python's default recursion limit is 1000, meaning that Python won't let a function call on itself more than 1000 times, which for most people is probably enough.

You can check the recursion limit on your machine by running the sys.getrecursionlimit() command. 

What Causes It To Be Exceeded?

The limit exists because allowing recursion to occur more than 1000 times doesn't exactly make for lightweight code.

For this reason, giving a large input to a recursive function results in a “maximum recursion depth exceeded” error. 

Bear in mind that you may see this error even if a recursive function calls itself less than 1000 times. This is because the recursion limit is not set to an exact number of recursions – it is set to the maximum depth of the stack.

Many developers encounter this error when running factorial, DFS, or similar algorithms with large inputs. 

Competitive programmers are no strangers to this error, either. It often makes an appearance on most platforms they use. 

How Can It Be Changed?

If, however, you find yourself in need of a higher recursion limit, there is a way to override the default limit and reset it to a number of your choice. This isn't exactly recommended, because it can definitely slow your code down, but on the occasion that it needs to be done, here's how you can do it:

How To Set The Recursion Limit

Let's say you want to set the limit to 1500. All you really need is to set a variable to 1500 followed by one line of code.

import sys
x=1500
sys.setrecursionlimit(x)

Remember: only take advantage of this method if it's absolutely essential.

Does The Recursion Limit Affect Performance?

Yes, increasing the recursion limit tends to slow down execution in order to accommodate for the large number of recursive calls.

Note that there is a ceiling to how high you can set the recursion limit, and the highest possible value is platform-dependent. If a program requires deep recursion, running it on a platform that supports the highest recursion limit is ideal. 

But even then, the recursion limit shouldn’t be set to a massive value, as it can crash the machine. 

Why “Does Maximum Recursion Depth Exceeded” Error Appear?

The typical recursive function is written with the recursive calls at the beginning of the function. The returned value of the recursion is then used to solve the function. 

In simple words, the final return value of a typical recursive function is only calculated when all the recursive calls return some value.  

However, this isn’t the case if you write a ‘tail recursive’ function. In these recursive functions, the statements and calculations are written first. The recursive call is made in the end.

This way, the statements and calculations of the original function are passed to the next recursive call. 

When this happens, the stack frame of the function being called is the only one that is needed. 

In other words, regular recursive functions push new entries into the call stack as necessary. The functions are popped from the stack when they return a value. But tail recursive functions use only one stack entry for all the recursive functions involved. 

This way, the tail recursive functions make for optimal memory utilization, as even with a large input, there is no chance for a stack overflow. This technique is known as tail recursion optimization.

Programming languages such as C and lisp support this kind of optimization. But unfortunately, Python’s interpreter is not equipped for this type of optimization. Python imposes a recursion limit of 1000 to prevent stack overflow. 

How to Increase the Size of the Stack to Run a Large Number of Recursions

Let’s say you wanted to run a recursive function that calls itself about a million times. You can try increasing the recursion limit to this number, which Python will allow you to do. 

However, when you try running the large recursive function, there’s a good chance of encountering a segmentation fault.

The good news is that you can increase the size of the Python stack to get around this issue. You can use the resource module from the standard library for this purpose, but this module is only available on Unix. It doesn’t work on macOS or Windows.

Running the resource.getrlimit() method will give you the soft and hard limit of the stack. So, you could run:

print(resource.getrlimit(resource.RLIMIT_STACK))
# (8388608, -1)

 Where resource.RLIMIT_STACK represents the current maximum size of the stack. In our example above, the softlimit is 8388608 B, which equals eight megabytes. The hard limit is -1, which means the hard limit is unlimited. 

You can change these values with the resource.setrlimit() method. Enabling deep recursion in Python is just a matter of changing the soft limit to a value appropriate to the number of recursive calls involved in your function. 

As an example, here’s a look at how you can set the soft limit to -1:

resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))