Python函数递归后返回None

Question

我搞不懂为什么这个Python函数在递归调用时会返回None。

这个函数是我解决Project Euler问题的一部分。虽然我已经用更好的方法解决了这个问题，但这个情况还是让我很烦恼，因为这个函数看起来工作得不错，而且似乎知道我想要返回的变量的值。

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

但是如果我把返回语句取消注释，它只有在第一次尝试是质数时才会返回一个值，否则就返回None。

Answer 1

注意到你在调用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 2

正如其他人所说，这里其实不太适合用递归。下面是一个使用循环的例子。我还定义了另一个函数，用来测试一个整数是否是质数——我觉得这样可以让代码更简单。

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)

Answer 3

你忘了在找不到质数的时候返回一个值：

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)

不过，这里其实不太适合用递归。用递归写出来的代码并没有比简单的循环方法更优雅。而且，如果你遇到两个连续的质数之间有很多非质数的情况，可能会导致栈溢出。