Python递归函数错误：“超过最大递归深度”
我用下面的代码解决了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)))这三个函数的工作方式如下：
- isPrime检查一个数字是否为prime;
- 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:最大递归深度超过。
我的递归函数做错了什么？或者是否有一些特定的方法来避免递归限制？
回答 5
Stack Overflow用户
发布于 2010-03-08 21:20:42
在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风格，但我喜欢one liners ^_^)
Stack Overflow用户
发布于 2010-03-08 21:58:26
正如我已经说过的，在不能处理深层堆栈的语言中，最好采用迭代方法。特别是在您的情况下，最好更改所使用的算法。我建议使用Sieve of Eratosthenes来查找质数列表。它会比你当前的程序快很多。
Stack Overflow用户
发布于 2010-03-08 21:19:47
好吧，我不是python专家，但我认为您已经达到了stack限制。这就是递归的问题，当你不需要递归很多次的时候，它是很好的，但是当递归的数量变得适度大的时候，它就不好了。
理想的替代方案是重写你的算法，改为使用迭代。
编辑：实际上仔细观察了你的具体错误，你可以通过改变sys.getrecursionlimit来克服它。不过，这只能带你走到这一步。最终，你会得到一个stackoverflow异常，这会让我回到我最初的观点。
https://stackoverflow.com/questions/2401447
复制相似问题