Python递归函数错误：“超出最大递归深度”
我用下面的代码解决了欧拉计划的问题 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，它与 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 给出了这样的信息：
运行时错误：超出了最大递归深度。
我的递归函数做错了什么？或者是否有一些特定的方法来避免递归限制？
I solved Problem 10 of Project Euler with the following code, which works through brute force:
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)))
The three functions work as follows:
- isPrime checks whether a number is a prime;
- primeList returns a list containing a set of prime numbers for a certain range with limit 'n', and;
- sumPrimes sums up the values of all numbers in a list. (This last function isn't needed, but I liked the clarity of it, especially for a beginner like me.)
I then wrote a new function, primeListRec, which does exactly the same thing as primeList, to help me better understand recursion:
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
The above recursive function worked, but only for very small values, like '500'. The function caused my program to crash when I put in '1000'. And when I put in a value like '2000', Python gave me this:
RuntimeError: maximum recursion depth exceeded.
What did I do wrong with my recursive function? Or is there some specific way to avoid a recursion limit?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
递归并不是 Python 中最惯用的处理方式，因为它没有尾递归优化因此使得使用递归代替迭代变得不切实际（即使在您的示例中该函数不是尾递归，但这也无济于事）。基本上，这意味着如果您希望输入很大，则不应将其用于复杂性大于线性的事物（仍然可以用于具有对数递归深度的事物，例如 QuickSort 等分而治之算法）。
如果你想尝试这种方法，请使用更适合函数式编程的语言，如 Lisp、Scheme、Haskell、OCaml 等；或者尝试 Stackless Python，它在堆栈使用方面有更广泛的限制，并且还具有尾递归优化:-)
顺便说一句，您的函数的尾递归等效项可能是：
另一个“顺便说一句”，您不应该构造一个列表，如果你只是使用它来添加值...解决欧拉项目第十个问题的 Pythonic 方法是：（
好吧，也许将它分成不同的行会更 Pythonic，但我喜欢一个衬垫 ^ _^)
Recursion is not the most idiomatic way to do things in Python, as it doesn't have tail recursion optimization thus making impractical the use of recursion as a substitute for iteration (even if in your example the function is not tail-recursive, that wouldn't help anyway). Basically, that means that you shouldn't use it for things that have a complexity greater than linear if you expect your inputs to be large, (still it's OK for doing things that have a logarithmic recursion depth, like divide and conquer algorithms as QuickSort).
If you want to try that approach, use a language better suited to do functional programming, as Lisp, Scheme, Haskell, OCaml, etc.; or give a try to Stackless Python, that has broader limits in stack usage and also has tail recursion optimisation :-)
By the way, a tail-recursive equivalent of your function could be:
Another "by the way", you shouldn't construct a list if you're using it just to add up the values... The Pythonic way to solve Project Euler's 10th problem is:
(OK, maybe splitting it in various lines would be even more Pythonic, but I love one liners ^_^)
正如已经说过的，在无法处理深堆栈的语言中，最好采用迭代方法。特别是在您的情况下，最好更改所使用的算法。我建议使用埃拉托斯特尼筛法来查找素数列表。它会比你当前的程序快得多。
Like already said, in languages that can't deal with deep stacks it's better to take an iterative approach. In your case, in particular, it's best to change the algorithm used. I suggest using the Sieve of Eratosthenes to find the list of prime numbers. It will be quite faster than your current program.
好吧，我不是 python 专家，但我想你已经达到了 堆栈 限制。这就是递归的问题，当你不必递归很多次时它很好，但当递归次数变得相当大时就不好了。
理想的替代方案是重写算法以使用迭代。
编辑：实际上，仔细查看您的具体错误后，您可以通过更改 sys.getrecursionlimit。但这只能带你到目前为止。最终你会得到一个 stackoverflow 异常，这让我回到了原来的观点。
Well I'm no python expert but I presume you've hit the stack limit. That's the problem with recursion, it's great when you don't have to recurse very many times but no good when the number of recursions gets even moderately big.
The ideal alternative is to rewrite your algorithm to use iteration instead.
Edit: Actually having looked closer your specific error you can get past it by changing sys.getrecursionlimit. That'll only take you so far though. Eventually you'll get a stackoverflow exception which brings me back to my original point.
您将迭代 n 个数字并在每一步递归。因此Python的递归限制定义了你的最大输入数。这显然是不可取的。特别是因为欧拉问题通常处理相当大的数字。
You're iterating over n numbers and recursing at each step. Therefore Python's recursion limit defines your maximum input number. That's obviously undesirable. Especially because the Euler problems typically deal with pretty large numbers.
你可以用一种肮脏的方式来做：
You can do it in a dirty way: