Python maximum recursion depth exceeded in comparison Solution

Recursive functions, without limits, could call themselves indefinitely. If you write a recursive function that executes over a certain number of iterations, you’ll encounter the “maximum recursion depth exceeded in comparison” Python error.

This guide discusses what this error means and why it is important. We’ll walk through an example of this error so you can learn how to fix it in your program.

maximum recursion depth exceeded in comparison

Recursive functions are functions that call themselves to find a solution to a program.

Well-written recursive functions include limits to ensure they do not execute infinitely. This may mean that a function should only run until a particular condition is met.

If you write a recursive function that executes more than a particular number of iterations (usually 997), you’ll see an error when you get to the next iteration.

This is because Python limits the depth of a recursion algorithm. This refers to how many times the function can call itself.

You can view the recursion limit in your Python shell using this code:

import sys
print(sys.getrecursionlimit())

An Example Scenario

Let’s write a recursive function that calculates a number in the Fibonacci Sequence. In the Fibonacci Sequence, the next number in the sequence is the sum of the last two numbers. The first two numbers in the sequence are 0 and 1.

Here is a recursive function that calculates the Fibonacci Sequence:

def fibonacci(n):
	if n <= 1:
		return n
	else:
		return(fibonacci(n-1) + fibonacci(n-2))

If the number we specify is less than or equal to 1, that number is returned. Otherwise, our program calculates the next number in the sequence.

Next, we’re going to call our function:

print(fibonacci(5000))


This code calculates the number after the 5,000th number in the Fibonacci Sequence. Let’s run our code and see what happens:

Traceback (most recent call last):
  File "main.py", line 7, in <module>
	print(recur_fibo(5000))
  File "main.py", line 5, in recur_fibo
	return(recur_fibo(n-1) + recur_fibo(n-2))
… 
  File "main.py", line 2, in recur_fibo
	if n <= 1:
RecursionError: maximum recursion depth exceeded in comparison

Our code returns a long error message. This message has been shortened for brevity.

The Solution

Python has raised a recursion error to protect us against a stack overflow. This is when the pointer in a stack exceeds the stack bound. Without this error, our program would try to use more memory space than was available.

We can fix this error by either making our sequence iterative, or by increasing the recursion limit in our program.

Solution #1: Use an Iterative Algorithm

We can change our program to use an iterative approach instead of a recursive approach:

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 code calculates the first five numbers in the Fibonacci Sequence. We could increase the number of values we calculate but that would also increase the time it takes for our program to execute. Our program returns:

1

1

2

3

5

This approach bypasses the recursion error because we do not use recursive functions. Instead, we use a while loop to calculate the next number in the list.

Solution #2: Increase Recursion Limit

You can override the default recursion limit Python sets using the setrecursionlimit() method:

import sys
sys.setrecursionlimit(5000)

This code sets the maximum recursion depth to 5,000. You should be careful when you use this method because it may cause a stack overflow depending on the resources available to the Python interpreter.

In general, it is best to rewrite a function to use an iterative approach instead of increasing the recursion limit.

"Career Karma entered my life when I needed it most and quickly helped me match with a bootcamp. Two months after graduating, I found my dream job that aligned with my values and goals in life!"

Venus, Software Engineer at Rockbot

Find Your Bootcamp Match

Conclusion

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.

Now you have the knowledge you need to fix this error like a pro!