3

I can't figure out why this python function returns None if it calls itself recursively.

It was part of my solution to a Project Euler problem. I have solved the problem in a better way anyhow, but this is still annoying me as the function seems to work OK - and it seems to know the value of the variable I wanted to return.

def next_prime(previous):
    if previous % 2 == 0:
        candidate = previous + 1
    else:
    candidate = previous + 2
    print "trying", candidate
    prime = True
    for div in range(2,candidate//2,1):
        if candidate % div == 0:
            prime = False
            print candidate, "is not prime - divisible by", div
            next_prime(candidate)
            break
    if prime is True:
        print candidate, "is prime"
        #return candidate

last = 896576
print "After", last, ", the next prime is..."
next_prime(last)

This gives:

After 896576 , the next prime is...
trying 896577
896577 is not prime - divisible by 3
trying 896579
896579 is not prime - divisible by 701
trying 896581
896581 is not prime - divisible by 7
trying 896583
896583 is not prime - divisible by 3
trying 896585
896585 is not prime - divisible by 5
trying 896587
896587 is prime

But if I uncomment the return statement it only returns a value if the first try is prime, otherwise it returns None.

Zero Piraeus
  • 56,143
  • 27
  • 150
  • 160
Simon Watkins
  • 2,135
  • 2
  • 13
  • 7

3 Answers3

6

You forgot to return a value when there is failure to find a prime:

for div in range(2,candidate//2,1):
    if candidate % div == 0:
        prime = False
        print candidate, "is not prime - divisible by", div
        return next_prime(candidate)

Recursion isn't really suitable here though. It isn't much more elegant than the simple iterative approach. Also, you could overflow the stack if you hit an area where there are lot of non-primes between two consecutive primes.

Mark Byers
  • 811,555
  • 193
  • 1,581
  • 1,452
1

As others have said, this is not really the place for recursion. Here is an example using iteration. I've also defined another function which tests the primality of an integer - I think this makes the code simpler.

def is_prime(n):
    """Return True if n is prime."""
    for i in xrange(2, n//2):
        if n%i == 0:
            return False
    return True

def next_prime(n):
    """Returns the next prime number after n."""
    if n % 2 == 0:
        candidate = n + 1
    else:
        candidate = n + 2
    while not is_prime(candidate):
        candidate += 2
    return candidate

if __name__ == '__main__':
    n = 896576
    print next_prime(n)
Gary Kerr
  • 13,650
  • 4
  • 48
  • 51
  • Yes - I have realised that this was the way to do it and I solved the problem in a similar way, I just couldn't see what I was doing wrong so I have given the correct answer to Mark, who was the first to point out my mistake. Thanks alot though. – Simon Watkins Jan 17 '10 at 21:43
0

Notice that you are making recursive calls to the next_prime function, but not returning the value from it from the calling function.

Replace the lines:

print candidate, "is not prime - divisible by", div
next_prime(candidate)

with

print candidate, "is not prime - divisible by", div
return next_prime(candidate)
MAK
  • 26,140
  • 11
  • 55
  • 86