Python递归函数错误: "maximum recursion depth exceeded"

Question

这个问题在这里已经有了答案:

What is the maximum recursion depth in Python, and how to increase it? (19 个回答)

关闭 5年前。

我使用以下代码解决了 Project Euler 的问题 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)))

三个函数的作用如下:

1. isPrime 检查一个数是否为素数；
2. primeList 返回一个列表，其中包含一组素数，其限制为“n”，并且；
3. 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: 超出最大递归深度。

我的递归函数做错了什么？还是有一些特定的方法可以避免递归限制？

Answer 1

递归并不是 Python 中最惯用的做事方式，因为它没有 tail recursion优化，从而使使用递归代替迭代变得不切实际(即使在您的示例中，该函数不是尾递归，这也无济于事)。基本上，这意味着如果您希望输入很大，则不应将其用于复杂性大于线性的事物(仍然可以用于具有对数递归深度的事物，例如分治算法，如 QuickSort )。

如果您想尝试这种方法，请使用更适合进行函数式编程的语言，例如 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，但我喜欢一个衬里^_^)