Most of the leading programming languages like Python impose a recursion depth limit, which is often 1,000, to protect users against a stack overflow. The maximum recursion depth is essentially the optimal number of times a program can carry out successive operations that are recursive.
If not checked, recursive operations could call themselves indefinitely. If a program exceeds the default recursion depth limit, it would require more memory than you probably have. To fix the issue, you may increase the recursion depth on your system.
This may be achieved by importing the sys module in your script, and then running the sys.setrecursionlimit() function. However, increasing the recursion depth may result in even more problems, hence not advisable. As you will learn in this guide, the best solution would be to rewrite the algorithm using an iterative sequence.
What Does Maximum Recursion Depth Mean?
Recursion is a scenario where you are defining something in terms of itself. In this regard, a recursive function is meant to solve a problem by calling itself over and over again repeatedly. This concept is an important part of data science and computer science.
A recursive function may be applied in cases where the solution can only be found by breaking the problem down into smaller problems that apply the same formula (commonly referred to as recursive algorithms). If you happen to execute a large recursive function in Python on large input, say > 10^4, you are likely to encounter the “MaximumRecursion Error: Depth Exceeded while calling a Python object” error.
This problem is common while executing such algorithms as factorial and DFS on larger inputs. It occurs because the Python interpreter is limiting the program to avoid infinite recursions. By default, a program on Python can only call on itself up to 1,000 times(which is the default recursion depth).
Iterative vs. Recursive Algorithms
Basically, there are two ways you may solve an algorithm in Python: iteratively or recursively. An interactive solution to an algorithm is often regarded as ‘powerful, but ugly.’ This is to say that they will get the job done, but will not achieve this in the most relevant way.
For instance, an iterative function will solve the problem using a loop. In other words, it executes the code within a loop, until the loop is complete. A recursive function, on the other hand, breaks the problem down into smaller parts and then solves each part by calling itself.
For instance, you may write a recursive function in Python to calculate a number in the Fibonacci Sequence. The next number in the Fibonacci Sequence is the sun of the last two numbers. Assuming that the first two numbers in this sequence are 0, and 1, then the function would be:
1 def fibonacci(n):
2 if n <= 1:
3 return n
5 return(fibonacci(n-1) + fibonacci(n-2))
With such a function, the number you specify will be returned, if it happens to be less than or equal to 1. Otherwise, the program will calculate the next number in the sequence. Having written the function, try to call the function to a number that is greater than the stack depth, as follows:
This tells the program to calculate the number after the 5,000th number in your Fibonacci Sequence. In this case, the code will return a long, “Recursion error Maximum recursion depth exceeded” message. Python will raise a recursion error to protect you against a stack overflow.
Without the recursion depth limit, the program would run infinitely and require more memory space than what is available.
What is Stack Overflow?
Stack overflow is a scenario whereby you are using more memory for a stack than the program is supposed to be using. Suppose you are using an embedded system that allocates just 256 bytes for the stack. Assuming that each function takes up 32 bytes of the memory space, you can only carry out 8 function calls deep.
In this case, function 1 will call function 2, function 2 call function 3, and so on until function 8 calls function 9. However, the function will simply overwrite the memory outside the stack. By so doing, it may end up overwriting the memory or even the entire code.
As a programmer, a wrong input in the function can cause it to go in circles infinitely. If you are writing your functions recursively (in such a way that the function calls itself), it is advisable to use static/global variables to prevent such an infinite recursion.
How to Fix the Maximum Recursion Depth Exceeded Error
Once the preset recursion depth limit on your system is reached, you will get a long recursion error message. This situation to notify you that the pointer in a stack has exceeded the present stack bound.
You can fix this problem by increasing the recursion limit on your system or making the sequence iterative, as illustrated below:
Solution 1: Increase the Maximum Recursion Depth Limit
This solution entails using the getrecursionlimit() function in Python to increase the maximum recursion depth limit. In the leading programming languages like Python, the system has limits set for recursive functions. These limits stipulate the optimal number of times a function can repeat itself.
By default, the maximum recursion depth is set at 1,000 in Python. If you feel that this limit is too low, you can increase the value. The correct syntax, in this case, would be:
This method does not accept parameters. As such, this is the function you should run:
1 import sys
This will configure your maximum recursion depth to 5,000. However, you will not need to enter such a large value, 1,500 times is probably enough.
Solution 2: Use an Iterative Algorithm Instead
If you are getting the maximum recursion depth exceeded error message, the best solution would be to write an iterative algorithm instead. For instance:
to_calculate = 5
i = 0
next = 1
current = 1
last = 0
while i < to_calculate:
next = current + last
current = last
last = next
i += 1
This iterative code will calculate the first five numbers within the Fibonacci Sequence. You may increase the number of values calculated by the program. However, increasing the number of values calculated will also increase the time taken by the program to execute the code. This solution will bypass the recursive error as it does not execute a recursive function. Instead, the program uses a while loop to calculate the next values in the sequence.
Configuring the maximum recursion depth value to a larger number can help you to overcome the recursion error message to a certain extent. Depending on the resources you have available to your Python interpreter, this method may lead to a stack overflow.
This being the case, the safer solution would be to rewrite your recursive function into an iterative algorithm. This is considered to be the best solution for this problem, as compared to increasing the recursion limit in Python.