Python递归函数错误："超过最大递归深度"

Question

Python递归函数错误："超过最大递归深度"

31

我用以下代码通过暴力破解方式解决了欧拉计划的第10个问题：

def isPrime(n):

    for x in range(2, int(n**0.5)+1):
        if n % x == 0:
            return False
    return True


def primeList(n):

    primes = []

    for i in range(2,n):
        if isPrime(i):
            primes.append(i)

    return primes


def sumPrimes(primelist):
    prime_sum = sum(primelist)
    return prime_sum


print (sumPrimes(primeList(2000000)))

以下是三个函数的作用:

isPrime 检查一个数字是否为质数；
primeList 返回一个包含一定范围内所有质数的列表，限制条件为'n'；
sumPrimes 对列表中所有数字的值求和。（这个函数不是必需的，但我喜欢它的清晰度，特别是对于像我这样的初学者。）

接着我编写了一个新的函数 primeListRec，它的功能与 primeList 完全相同，帮助我更好地理解递归：

def primeListRec(i, n):
    primes = []
    #print i


    if (i != n):
        primes.extend(primeListRec(i+1,n))

    if (isPrime(i)):
        primes.append(i)
        return primes


    return primes

上述递归函数可以运行，但仅适用于非常小的值，例如“500”。当我尝试输入“1000”时，该函数导致我的程序崩溃。而当我输入像“2000”这样的值时，Python给出了这个错误信息：

RuntimeError: maximum recursion depth exceeded。

我的递归函数哪里出了问题？或者有没有一些特定的方法可以避免递归限制？

- xax

5个回答

2

如前所述，在不能处理深度堆栈的语言中，采用迭代方法更为可取。对于您的情况，最好改变所使用的算法。我建议使用埃拉托斯特尼筛法来查找质数列表。它比您当前的程序要快得多。

- Thiago Chaves

我的程序确实很慢。花费了一分钟以上的时间才完成，这违反了欧拉计划的“一分钟规则”。我刚刚了解了埃拉托色尼筛法，它非常有趣。我会尽力学习。感谢你的建议。 - xax

1

虽然我不是Python专家，但我猜你已经达到了堆栈限制。这就是递归的问题，当你不需要递归很多次时，它非常好用，但是当递归次数变得相当大时，它就无法胜任。

理想的替代方案是重写算法，改用迭代。

编辑：实际上，仔细查看你的特定错误，你可以通过更改sys.getrecursionlimit来解决它。不过，这只能帮你走那么远。最终，你会遇到堆栈溢出异常，这也证明了我的原始观点。

- Adrian

我不太明白。第一个算法“primeList”不是已经基于迭代了吗？此外，问题使用了200万的值；这是否是一个扩展的不合理限制？ - xax

确实是这样。但你问为什么你的第二个primeListRec函数没有起作用。它是递归的，因此递归深度超过了错误限制。 - Adrian

0

你正在迭代n个数字，并在每一步递归。因此，Python的递归限制定义了您的最大输入数字。这显然是不可取的。特别是因为欧拉问题通常涉及相当大的数字。

- Johannes Charra

那么我必须始终依靠使用for/while循环手动迭代处理大量数据吗？ - xax

是的，我想是这样...虽然不是完全确定。可能有例外情况，但我无法清楚地区分它们 :) - Johannes Charra

我一定会寻找你提到的异常。谢谢！ - xax

-3

你可以用一种不太规范的方式来实现：

try: function() except: function()

- Riptide00

1

好的，我收回之前的话。 - Riptide00

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- fortran · Accepted Answer

递归在Python中不是最惯用的做事方式，因为它没有尾递归优化，因此如果期望输入较大，则使用递归作为迭代的替代方法是不切实际的（即使在您的示例中函数不是尾递归，也无济于事）。基本上，这意味着如果您期望输入较大，则不应将其用于具有大于线性复杂度的任务（但仍然可以用于具有对数递归深度的任务，例如快速排序等分治算法）。

如果您想尝试该方法，请使用更适合进行函数式编程的语言，如Lisp、Scheme、Haskell、OCaml等；或者尝试Stackless Python，它在堆栈使用方面具有更广泛的限制，并且还具有尾递归优化 :-)

顺便说一句，一个等价于您函数的尾递归版本可能是：

def primeList(n, i=2, acc=None):
    return i > n and (acc or []) or primeList(n, i+1, (acc or []) + (isPrime(i) and [i] or []))

另外，如果你只是用列表来累加值的话，你不应该构建一个列表... 解决Project Euler第10个问题的Pythonic方法是：

print sum(n for n in xrange(2, 2000001) if all(n % i for i in xrange(2, int(n**0.5)+1)))

好的，也许将其拆分为多行可能更符合Pythonic，但我喜欢一行 ^_^