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!

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?

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.