我的代码在python中通过递归找到素数是正确的吗？还是答案的关键？

Question

我正在学习Python，这本书是由Mr.John Hunt编写的“python3入门指南”。在关于递归的第8章中，有一个练习，它要求一个代码，其中一个素数是通过递归找到的。我独立地编写了下面的第一段代码，但答案键是用不同的结构编写的。因为我对递归很怀疑，你对这两种情况的分析是什么？哪个是递归的？

我的代码：

def is_prime(n, holder = 1):
    if n == 2:
        return True
    else:
        if (n-1 + holder)%(n-1) == 0:
            return False
        else:
            return is_prime(n-1, holder+1)

print('is_prime(9):', is_prime(9))
print('is_prime(31):', is_prime(31))

答案键：

def is_prime(n, i=2):
    # Base cases
    if n <= 2:
        return True if (n == 2) else False
    if n % i == 0:
        return False
    if i * i > n:
        return True

    # Check for next divisor
    return is_prime(n, i + 1)

print('is_prime(9):', is_prime(9))
print('is_prime(31):', is_prime(31))

Answer 1

在这种情况下，我的建议是不要在所有上使用递归。虽然我理解您希望将此作为如何使用来使用递归的学习示例，但在使用递归时学习也很重要。

递归具有最大允许深度，因为递归越深，需要在调用堆栈上放置更多的项。因此，这不是一个使用递归的好例子，因为在这种情况下很容易达到最大值。即使是“模型”示例代码也会受到这种影响。确切的最大递归深度可能与实现有关，但例如，如果我试图使用它计算is_prime(1046527)，则会得到一个错误：

RecursionError: maximum recursion depth exceeded while calling a Python object

插入print(i)语句显示，当i=998时会遇到它。

一个简单的非递归等价的“模型”例子将不会有这个问题。(有更有效的解决方案，但除了不使用递归之外，这个解决方案还试图接近模型解决方案。)

def is_prime(n):
    
    if n == 2:
        return True

    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1

    return True

(实际上，您可能也希望处理n<2案例。)

如果您想要一个更好的问题示例来练习递归编程，请查看河内塔问题。在这种情况下，您会发现使用递归可以使您做出比没有递归更简单、更干净的解决方案，而不可能超过最大递归深度(您不需要考虑一个1000磁盘高的塔，因为解决方案需要大量的移动，2^1000-1或大约10^301)。

作为使用递归的另一个很好的例子，尝试使用海龟图形来绘制科赫雪花。

Answer 2

我认为应答键需要改进。我们可以使它更快，并更干净地处理基本案例：

def is_prime(n, i=3):
    # Base cases
    if n < 2:
        return False

    if n % 2 == 0:
        return n == 2

    if i * i > n:
        return True

    if n % i == 0:
        return False

    # Check for next divisor
    return is_prime(n, i + 2)

最初的答案键从2开始到1开始--这里我们从3开始，再倒数2。

就你的回答而言，还有一个不同的缺陷需要考虑。Python的默认堆栈深度是1,000帧，您的函数在输入1,000上面不久就会失败。上面的解决方案更少地使用递归，在达到Python的默认堆栈限制之前，可以处理多达4,000,000的输入。

Answer 3

是的，你的例子似乎是正确的。但是请注意，根据实现的性质，答案键更有效。为了验证一个数字n是素数，您的算法使用最大的n-1函数调用，而提供的答案在达到sqrt(n)的迭代计数后停止。检查较高的数字通常是没有意义的，因为如果n是可以被a > sqrt(n)值除的，那么它也必须被b=n%a整除。

此外，您的代码在n=1时会引发一个异常，因为没有定义0的模。