Recursion function for prime number check

Question

I have this code:

def has_divisors(n, i=2):
 """
 Check if a number is prime or not
 :param n: Number to check
 :param i: Increasing value that tries to divide
 :return: True if prime, False if not
 """
 if n <= 1:
 return False
 if i + 1 == n:
 return True
 if n <= 2 and n > 0:
 return True
 if n % i == 0:
 return False
 return has_divisors(n, i + 1)

Which tell if a number is prime or not, problem is that it can check if a number is prime up to +- 1500 after that it enters into maximum recursion depth error. Does anyone has any idea how to make this code more efficient and get to higher numbers (I don't want a completely different code if possible, yes I know recursion is not a good idea for this function but I have to use it) Thank you!

• AJNeufeld: Can you explain, or expand upon, what exactly the reason is for a recursive method to be required? Does it have to use this exact function signature? Can a recursive helper function be used instead? I ask because testing 997 results in close to one thousand redundant checks of n <= 1, n <= 2, and n > 0. With a better understanding of the exact constraints, more efficient solutions will be possible.

Answer 1

Python and recursion are not a good mix, because Python doesn't do tail call optimization. (There's a fun blog post here that explores a cheesy workaround that you probably don't want to do for this project: https://chrispenner.ca/posts/python-tail-recursion)

Leaving that aside, there are two opportunities I see for optimization:

if i + 1 == n:
 return True

The largest minimum factor of any given number is going to be its square root, so you don't need to look for factors all the way up to n.

return has_divisors(n, i + 1)

If n wasn't divisible by 2, it's not going to be divisible by any other even number, so this recursive call is a waste of time (and stack space) at least half the time. Are there any other ways you might be able to know before you recurse that a given new value of i isn't going to be fruitful?

• slepic: Recursion is always suboptimal. Not just in Python...
• AMC: @slepic That's a bold claim.
• AMC: @slepic Somehow I missed the Not just in Python part. That's not even bold, just silly.
• Samwise: Okay, look. With a decent compiler/interpreter, equivalent recursive/iterative constructs boil down to the same machine instructions, so the efficiency argument goes out the window, which leaves you with "what's easier for a human reader to understand?" And that's something that you can probably make an argument for being generally more intuitive one way or the other in a broad set of circumstances, but if someone is enough of a zealot to even attempt the argument that doing it one particular way is easier for 100% of people 100% of the time, it's not worth arguing. Just nod and smile.
• Samwise: nods and smiles

Answer 2

Basically your function boils down to.

def has_div(n,i=2):
 return n>1 and (i*i>n or (n%i!=0 and has_div(n,i+1))) 

which is the same as

def has_div2(n,i=2):
 if n<=1:
 return False
 if i*i > n :
 return True
 if n%i == 0:
 return False
 return has_div2(n,i+1)

The two functions work for 997991 and report recursion depth exceeded for 998009 which are 78359th and 78360th prime numbers.