How to make this recursion function for prime number more efficient

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 (I don't want completely different code, yes I know recursion is not a good idea for this function but I have to use it) Thank you!

One way is [to increase the max recursion depth](https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it). That being said you should really remove recursion and use a loop instead. — freakish, Dec 17 '19 at 20:41
After 2, you don't have to check any even numbers as factors, and you don't have check any factors whose square is greater then n. — khelwood, Dec 17 '19 at 20:41
I know this appears to be a practice exercise (why else is recursion a requirement?), but for others who stumble on this question: a practical option is just to use a library that is already optimized for this. For example, `import sympy` followed by `sympy.isprime( n )` — Jason K Lai, Dec 17 '19 at 20:45
[How do I find a prime number using recursion in Python](https://stackoverflow.com/questions/37095508/how-do-i-find-a-prime-number-using-recursion-in-python) second answer has a similar function that can go 1M rather than 1K before hitting max recursion depth. — DarrylG, Dec 17 '19 at 20:51
Just to state the obvious, there is no need to use recursion to check primality. So the fact that some solution can handle 1M excursions is pointless. — Chris Johnson, Dec 17 '19 at 21:10

score 0 · Accepted Answer · answered Dec 17 '19 at 21:06

I actually made it more efficient by just adding one condition:

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 == n:
    return True
if n <= 2 and n > 0:
    return True
if i * i > n:
    return True
if n % i == 0:
    return False
return has_divisors(n, i + 1)

Thanks to everyone who tried to help.

score 0 · Answer 2 · answered Dec 17 '19 at 21:07

Modifying function from How do I find a prime number using recursion in Python

This should have a maximum recursion dept > 1M

Two improvements: only goes to sqrt(N), and only checks odd numbers.

def has_divisors(N, i=3):
  if N <= 2:
      return False
  elif N % 2 == 0:  # even
      return True
  elif i * i > N:  # tried all divisors to sqrt, 
                   # must be prime
      return False

  elif (N % i) == 0:  # i is a divisor
    return True
  else:  # recursively try the next ( odd) divisor
      return has_divisors(N, i + 2)

score 0 · Answer 3 · answered Dec 17 '19 at 22:34

You don't need to do basic disqualifying tests on every recursion, so to make it more efficient, as you requested, I'd cast it like:

def has_no_divisors(n):

    if n <= 2 or n % 2 == 0:
        return n == 2

    def has_no_divisors_recursive(n, i=3):

        if i * i > n:
            return True

        if n % i == 0:
            return False

        return has_no_divisors_recursive(n, i + 2)

    return has_no_divisors_recursive(n)

By treating 2 as a special case and just test dividing odd numbers, this should also have twice the performance (and half the stack usage) of your revised code.

How to make this recursion function for prime number more efficient

3 Answers3