Python RecursionError

Question

(I'm a total beginner) I want to write a recursive function which can tell me if a number is a prime number or not: but I keep getting the same recursion error : here is my code :


from math import *
def has_a_divider(n,p):
    if n%p==0:
        return True
    elif has_a_divider(n,(p-1))!= True:
        return False
    else:
        return False


def is_prime(a):
    if has_a_divider(a,sqrt(a))==False:
        return True
    else:
        return False

There is a recursion depth limit in python [see](https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it) — oo00oo00oo00, Jun 05 '20 at 12:02
`sqrt(a)` returns float, not int. Maybe you wanted to use `int(sqrt(a))`. It is not solving your problem, but it could improve the result. — Pavel Botsman, Jun 05 '20 at 12:02

Sylvaus · Answer 1 · 2020-06-05T12:10:51.600

0

Your problem is sqrt(a) which returns a float instead of the int your code requires.
You can replace it by ceil(sqrt(a)) to get an int from it.

Also, this code does not work for finding if the number is prime as all numbers will have at least 1 has a divider. A possible solution is to update has_a_divider to check for dividers bigger than 1.

A possible implementation:

from math import ceil, sqrt
def has_a_divider(n,p):
    if p < 2:
        return False
    if n % p==0:
        return True
    return has_a_divider(n,(p-1))


def is_prime(a):
    if a == 1:
        return False

    return not has_a_divider(a,ceil(sqrt(a)))

print(is_prime(3))
print(is_prime(5))
print(is_prime(4))

edited Jun 05 '20 at 12:10

answered Jun 05 '20 at 12:03

Sylvaus

844
6
13

the __real__ issue (wrt/ infinite recursion I mean) is the lack of a guard before the recursive call - which your updated answer adds with the test on `p > 2`. – bruno desthuilliers Jun 05 '20 at 12:10
@brunodesthuilliers. Let me disagree, if the input is an int there is an end case since at one point p will become one and `n % p` will always evaluate to 0. Additionally, dividers do not make much sense for floats. You can test it for yourself, remove the `p < 2` and run the code, you will *not* get infinite recursion. – Sylvaus Jun 05 '20 at 12:13
I'm talking about the general case - making sure you DO have an end case in recursive calls. In this _specific_ case, forcing `p` to an int does indeed creates such a guard, but that's not the case for all recursive functions. This being said, since using floats as dividers don't make much sense in this context, you do have a point Sir ;-) – bruno desthuilliers Jun 05 '20 at 12:20
Then do you agree that your first comment is wrong in this instance since this answer is for this particular case where `has_divider` is expecting an int ? Or do you expect a function to behave appropriately in Python when the wrong type is given as parameter ? (Personally, I prefer the GIGO approach) – Sylvaus Jun 05 '20 at 12:27
@Sylvaus I do agree that I was thinking in general terms and didn't fully analysed the consequences of forcing `p` into an int is this specific case, yes. I thought I made that point clear in my previous comment ;-) – bruno desthuilliers Jun 05 '20 at 12:32

Python RecursionError

1 Answers1