1

我想知道这个程序如何知道一个数字是否是素数。我知道它会检查余数以找到要除以的偶数，但它怎么知道一个数字只有 2 个因数？我是递归概念的新手，所以对这些步骤的解释会很有帮助，谢谢。

代码

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

4

2 回答 2

2

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

EG，因为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，所以and不会评估 的右侧。PrimeHelper(10, 5)将返回false并且不会继续递归。
In PrimeHelper(10, 6)you get 10 % 6 != 0to be true，但我们刚刚看到PrimeHelper(10, 5)be false，所以这也将返回 false ，所有其他调用也将返回 false 。

于 2016-11-05T13:47:10.063 回答
0

这段代码是一个尾递归案例，即它可以被看作是执行迭代的递归方式。请注意，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了

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

return PrimeHelper(m, m -1)

经过

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

这也解决了 1 的情况：1是否为质数不仅仅是“有争议的” ：绝对不是。

于 2016-11-05T13:52:09.953 回答