Fonction Python renvoyée Aucune après la récursion

Question

Je n'arrive pas à comprendre pourquoi cette fonction python renvoie None si elle s'appelle récursivement.

Cela faisait partie de ma solution à un problème de Project Euler. J'ai résolu le problème de toute façon, mais cela m'énerve encore car la fonction semble fonctionner correctement - et il semble connaître la valeur de la variable que je voulais retourner.

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) 

Cela donne:

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 

Mais si je décommenter la déclaration de retour, il retourne une seule valeur si le premier essai est premier, sinon il retourne Aucun.

Answer 1

Vous avez oublié de retourner une valeur quand il y a défaut de trouver un premier:

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) 

récursivité est pas vraiment adapté ici bien. Ce n'est pas beaucoup plus élégant que la simple approche itérative. En outre, vous pouvez déborder la pile si vous frappez une zone où il y a beaucoup de non-premiers entre deux nombres premiers consécutifs.

Answer 2

Notez que vous effectuez des appels récursifs à la fonction next_prime, mais que vous n'en renvoyez pas la valeur à partir de la fonction appelante.

Remettez en place les lignes:

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

avec

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

Answer 3

Comme d'autres l'ont dit, ce n'est pas vraiment l'endroit idéal pour récursivité. Voici un exemple utilisant l'itération. J'ai également défini une autre fonction qui teste la primalité d'un entier - je pense que cela simplifie le code.

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)