You might have seen a Python recursion error when running your Python code. Why does this happen? Is there a way to fix this error? Show
A Python RecursionError exception is raised when the execution of your program exceeds the recursion limit of the Python interpreter. Two ways to address this exception are increasing the Python recursion limit or refactoring your code using iteration instead of recursion. Let’s go through some examples so you can understand how this works. The recursion begins!
Let’s create a program to calculate the factorial of a number following the formula below: n! = n * (n-1) * (n-2) * ... * 1 Write a function called factorial and then use print statements to print the value of the factorial for a few numbers.
This is a recursive function… A recursive function is a function that calls itself. Recursion is not specific to Python, it’s a concept common to most programming languages. You can see that in the else statement of the if else we call the factorial function passing n-1 as parameter. The execution of the function continues until n is equal to 0. Let’s see what happens when we calculate the factorial for two small numbers:
After checking that __name__ is equal to ‘__main__’ we print the factorial for two numbers. It’s all good. But, here is what happens if we calculate the factorial of 1000…
The RecursionError occurs because the Python interpreter has exceeded the recursion limit allowed. The reason why the Python interpreter limits the number of times recursion can be performed is to avoid infinite recursion and hence avoid a stack overflow. Let’s have a look at how to find out what the recursion limit is in Python and how to update it. What is the Recursion Limit in Python?Open the Python shell and use the following code to see the value of the recursion limit for the Python interpreter:
Interesting…the limit is 1000. To increase the recursion limit to 1500 we can add the following lines at the beginning of our program:
If you do that and try to calculate again the factorial of 1000 you get a long number back (no more errors).
That’s good! But… …this solution could work if like in this case we are very near to the recursion limit and we are pretty confident that our program won’t end up using too much memory on our system. How to Catch a Python Recursion ErrorOne possible option to handle the RecursionError exception is by using try except. It allows to provide a clean message when your application is executed instead of showing an unclear and verbose exception. Modify the “main” of your program as follows:
Note: before executing the program remember to comment the line we have added in the section before that increases the recursion limit for the Python interpreter. Now, execute the code… You will get the following when calculating the factorial for 1000.
Definitely a lot cleaner than the long exception traceback. Interestingly, if we run our program with Python 2.7 the output is different:
We get back a NameError exception because the exception of type RecursionError is not defined. Looking at the Python documentation I can see that the error is caused by the fact that the RecursionError exception was only introduced in Python 3.5: So, if you are using a version of Python older than 3.5 replace the RecursionError with a RuntimeError.
In this way our Python application works fine with Python2:
How Do You Stop Infinite Recursion in Python?As we have seen so far, the use of recursion in Python can lead to a recursion error. How can you prevent infinite recursion from happening? Is that even something we have to worry about in Python? Firstly, do you think the code we have written to calculate the factorial could cause an infinite recursion? Let’s look at the function again…
This function cannot cause infinite recursion because the if branch doesn’t make a recursive call. This means that the execution of our function eventually stops. We will create a very simple recursive function that doesn’t have an branch breaking the recursion…
When you run this program you get back “RecursionError: maximum recursion depth exceeded”.
So, in theory this program could have caused infinite recursion, in practice this didn’t happen because the recursion depth limit set by the Python interpreter prevents infinite recursion from occurring. How to Convert a Python Recursion to an Iterative ApproachUsing recursion is not the only option possible. An alternative to solve the RecursionError is to use a Python while loop. We are basically going from recursion to iteration.
Firstly we set the value of the factorial to 1 and then at each iteration of the while loop we:
The execution of the while loop continues as long as n is greater than 0. I want to make sure that this implementation of the factorial returns the same results as the implementation that uses recursion. So, let’s define a Python list that contains a few numbers. Then we will calculate the factorial of each number using both functions and compare the results. We use a Python for loop to go through each number in the list. Our program ends as soon as the factorials calculated by the two functions for a given number don’t match.
Let’s run our program and see what we get:
Great! Our implementation of the factorial using an iterative approach works well. ConclusionIn this tutorial we have seen why the RecursionError occurs in Python and how you can fix it. Two options you have are:
Which one are you going to use? Related posts:I’m a Tech Lead, Software Engineer and Programming Coach. I want to help you in your journey to become a Super Developer! What does recursion error mean?In some ways, recursion is analogous to a loop. Both execute the same code multiple times, and both require a condition (to avoid an infinite loop, or rather, infinite recursion in this case). When there are too many function calls, or a function is missing a base case, JavaScript will throw this error.
How do you fix a recursive error?The “maximum recursion depth exceeded in comparison” error is raised when you try to execute a function that exceeds Python's built in recursion limit. You can fix this error by rewriting your program to use an iterative approach or by increasing the recursion limit in Python.
How do you stop recursion error in Python?Try increasing the recursion limit ( sys. setrecursionlimit ) or re-writing your code without recursion. 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.
How do I fix maximum recursion depth exceeded in Python?The recursion depth limit in Python is by default 1000 . You can change it using sys. setrecursionlimit() function.
|