Python递归函数错误：“超出了最大递归深度”

Question

我使用以下代码解决了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中最惯用的方法，因为它没有尾递归优化，因此使用递归代替迭代是不切实际的（即使在您的示例中该函数不是尾递归，也不会仍然没有帮助）。基本上，这意味着如果您希望输入较大，则不应该将其用于复杂度大于线性的事物（（对于具有对数递归深度的事物，例如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 []))

另一个“顺便说一句”，如果仅使用它来求和值，则不应构造一个列表。解决欧拉计划第10个问题的Python方法是：

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

（好吧，也许将其拆分成更多行会更加Pythonic，但是我喜欢一个内衬^ _ ^）