素数递归是如何工作的？（Python）

Question

我想知道这个程序怎么知道一个数是不是素数。我知道它会检查余数，找出要除以的偶数，但它怎么知道一个数只有两个因子？我对递归的概念还不熟悉，所以对这些步骤的解释会很有帮助的，谢谢。在

编码

def RecIsPrime(m):
    """Uses recursion to check if m is prime."""
    def PrimeHelper(m, j):
        """Helper Function to iterate through all j less than m up to 1 to look for even divisors."""
        if j == 1:  # Assume 1 is a prime number even though it's debatable.
            return True
        else:
            #do this task if both conditionals are true
            #else break and return false.
            return m % j != 0 and PrimeHelper(m, j - 1)
    return PrimeHelper(m, m -1)

来源

https://github.com/hydrogeologist/LearningPython/blob/master/_recursion%20example%20in%20Python

线路：184至194

Answer 1

这段代码是一个尾部递归的情况，也就是说，它可以看作是执行迭代的递归方式。请注意，Python实际上并不是这样解释的（这是一种优化），但是这样看还是有帮助的：

看看PrimeHelper的每个递归调用对m的值是如何相同的，但是对于j的值与在上一次调用中的值相比少了一个。在

因此，代码与此变体相当：

def RecIsPrime(m):
    for j in range(m-1, 1, -1):
        if m % j == 0:
            return False
    return m > 1

在这个变量中，每次迭代都对应于原始代码中的递归调用。请注意，return False断开了链，这是由m % j != 0在原始代码中完成的，即它有两个用途：

1. 返回False
2. 不再呼叫PrimeHelper

需要注意的是，当您使用小于等于1的参数调用RecIsPrime时，这两个变量的行为方式不同。在这些情况下，递归代码可以产生“除以零”错误（当RecIsPrime(1)）或永远递归（例如RecIsPrime(-1)或任何更小的值）。这是个虫子。要更正它，请更改：

^{pr2}$

通过

return m > 1 and PrimeHelper(m, m -1)

这也修正了1的情况：1是否是质数不仅仅是一个值得商榷的问题：它绝对不是。在

Answer 2

它检查是否有从m-1到1的数除以m，它不检查偶数。在

例如，对于RecIsPrime(10)，您将有这些嵌套函数调用：

PrimeHelper(10, 9) = 10 % 9 != 0 and PrimeHelper(10, 8)
↪ PrimeHelper(10, 8) = 10 % 8 != 0 and PrimeHelper(10, 7)
  ↪ PrimeHelper(10, 7) = 10 % 7 != 0 and PrimeHelper(10, 6)
    ↪ PrimeHelper(10, 6) = 10 % 6 != 0 and PrimeHelper(10, 5)
      ↪ PrimeHelper(10, 5) = 10 % 5 != 0 == false

10 % 5 != 0是false，所以{}的右手边不会被计算。PrimeHelper(10, 5)将返回false，并且不会继续递归。
在PrimeHelper(10, 6)中，10 % 6 != 0为true，但我们刚刚看到{}是{}，因此这也将返回false，其他所有调用也将返回false。在