Amiel Moodley - 5 months ago 15x
Python Question

# How do I find a prime number using recursion in Python

I have to find out whether number(N) is a prime or not using recursion, no loops are allowed. I've tried converting the usual code that uses a for loop to a recursive one, but it's not behaving the same. This function is included in another function, which is part of another function. only parameters a and N should be used and passed
Here is my function.

``````a=2
def is_prime(a,N):
prime = True
if N <=1:
return
else:
if a >= N:
return
else:
if N == 2:
prime = True
print(N)
return
elif (N % a) == 0:
prime = False
return is_prime(a+1,N)
else:
prime = True
print(N)

return
``````

I believe the bug is somewhere here.

``````elif (N % a) == 0:
prime = False
return is_prime(a+1,N)
else:
prime = True
print(N)
``````

Here is the code I tried to convert.

``````if num > 1:
for i in range(2,num):
if (num % i) == 0:
print(num,"is not a prime number")
print(i,"times",num//i,"is",num)
break
else:
print(num,"is a prime number")

else:
print(num,"is not a prime number")
``````

Your solution is close, with just a few changes needed to make it work.

``````def is_prime(a,N):
print(a, N)
if N <= 1:
return
else:
if a >= N:
print(N)
else:
if N == 2:
print(N)
elif (N % a) == 0:
return False
else:
return is_prime(a+1,N)

return False
``````

You didn't give any examples of calling this function, but I assume it's always called with `a` being 2, since any other value wouldn't make sense. So if you run the above function like so, you should get the right output:

``````print(is_prime(2, 7))  => True
print(is_prime(2, 4))  => False
print(is_prime(2, 37)) => True
``````

I think you have a misunderstanding of how recursion works, you're assigning this `prime` variable in the body of the function, but never doing anything with it. Maybe you're confusion comes from a misunderstanding of scopes in Python. That `prime` variable will not be 'shared' across invocations, it will just create a new `prime` every time.

EDIT: Didn't realize you wanted the function to just print out the prime if it's a prime, changed the code accordingly.