Python的递归函数错误：“最大递归深度超过”

我解决问题10项目欧拉的用下面的代码，它通过蛮力的工作原理：Python的递归函数错误：“最大递归深度超过”

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：超过最大递归深度。

我的递归函数有什么问题？还是有一些具体的方法来避免递归限制？

来源

2010-03-08 anonnoir

递归并不是Python中最常用的方法，因为它没有tail recursion优化，因此使用递归作为迭代的替代物是不切实际的（即使在你的例子中函数不是尾递归的，这无济于事）。基本上，这意味着如果你希望你的输入很大，你就不应该将它用于复杂度大于线性的事情（对于做对数递归深度的事情也是可以的，比如分而治之算法就像QuickSort ）。

如果您想尝试这种方法，请使用更适合做函数式编程的语言，比如Lisp，Scheme，Haskell，OCaml等。;或给一个尝试无堆栈的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 []))

另一个“顺便说一下”，你不应该，如果你使用它只是增加了价值构建一个列表...在Python的方式来解决项目欧拉的第10个问题是：

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

（OK，也许分裂它在各种各样的线将更加Pythonic，但我爱一个内线^ _ ^）

来源

2010-03-08 13:20:42 fortran

然后在Python中使用可行的方法递归吗？大多数Python程序员是否会避免它？（即它是否是Pythonic？） – anonnoir

由于递归调用不是函数中的最后一个操作，尾递归在这种情况下不起作用。 –

当迭代版本无论如何需要堆栈时（例如遍历一棵树，产生排列等）并且递归深度被限制到合理的大小时，这是一种可行的方法。在这种情况下，您试图以人为的方式使用递归，因为它显然是您需要的循环。 – fortran

嗯，我不是蟒蛇专家，但我认为你已经达到了stack限制。这是递归的问题，当你不需要递归很多次，但是当递归的数量变得很大时没什么用处。

理想的选择是重写你的算法来代替使用迭代。

编辑：实际上，通过更改sys.getrecursionlimit来查看更具体的错误，您可以通过它。尽管如此，这只会带你到目前为止。最终你会得到一个stackoverflow例外，这使我回到我原来的观点。

来源

2010-03-08 13:19:46 Adrian

我不太明白。是不是第一种算法，即'primeList'，已经基于迭代？此外，该问题使用200万的值;这是扩大到不合理的限制吗？ – anonnoir

的确如此。但你问为什么你的第二个primeListRec没有工作。它是递归的，因此递归深度超过了错误。 – Adrian

我明白了。谢谢。 – anonnoir

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

来源

2010-03-08 13:32:50

因此，我必须坚持通过for/while循环进行大量手动迭代吗？ – anonnoir

是的，我认为是的......虽然不完全确定。规则可能有例外，但我无法清楚地区分它们。 :) –

我一定会寻找你提到的例外。谢谢！ – anonnoir

就像已经说过的，在无法处理深度堆栈的语言中，最好采用迭代方法。在你的情况下，特别是最好改变使用的算法。我建议使用Sieve of Eratosthenes来查找素数列表。它会比你现在的程序快得多。

来源

2010-03-08 13:58:26

确实，我的程序很慢。花了一分多钟才完成，这打破了欧拉的“一分钟规则”。我刚刚查看了Eratosthenes的Sieve方法，这很吸引人。我会尽我所能去学习它。感谢您的建议。 – anonnoir

-2

你可以做一个肮脏的方式：

try: function() except: function()

来源

2015-12-12 04:36:18 Riptide00

好的，我收回它 – Riptide00

Python的递归函数错误：“最大递归深度超过”

回答

相关问题