递归返回无Python函数

Question

我不明白为什么这个python函数返回无，如果它递归调用自己。

这是我解决项目欧拉问题的一部分。无论如何，我已经以更好的方式解决了这个问题，但是这仍然让我很烦恼，因为这个函数似乎可以正常工作 - 而且它似乎知道我想要返回的变量的值。

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) 

这给：

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 

但是，如果我去掉了return语句，如果第一次尝试是素数只返回一个值，否则返回无。

Answer 1

你忘了返回一个值，当出现故障时找到一个素数：

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) 

递归是不是真的适合这里虽然。它并不比简单的迭代方法更优雅。另外，如果你碰到两个连续的素数之间有很多非素数的区域，你可能会溢出堆栈。

Answer 2

请注意，您正在对next_prime函数进行递归调用，但不会从调用函数返回值。

更换线路：

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

与

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

Answer 3

正如其他人所说，这是不是真的递归的地方。这是一个使用迭代的例子。我还定义了另一个测试整数的素数的函数 - 我认为这使得代码更简单。

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)