Python递归函数报错:“超出最大递归深度" [英] Python recursive function error: "maximum recursion depth exceeded"
问题描述
我使用以下代码解决了 Project Euler 的第 10 个问题,该代码通过暴力破解:
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)))
三个函数的作用如下:
- isPrime 检查一个数是否是素数;
- primeList 返回一个列表,其中包含一组以n"为界限的特定范围内的质数,并且;
- sumPrimes 对列表中所有数字的值求和.(不需要最后一个功能,但我喜欢它的清晰性,特别是对于像我这样的初学者.)
- 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.)
然后我编写了一个新函数 primeListRec,它的作用与 primeList 完全相同,以帮助我更好地理解递归:
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
上述递归函数有效,但仅适用于非常小的值,例如500".当我输入1000"时,该函数导致我的程序崩溃.当我输入一个像2000"这样的值时,Python 给了我这个:
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:
运行时错误:超出最大递归深度.
我的递归函数做错了什么?或者是否有一些特定的方法可以避免递归限制?
What did I do wrong with my recursive function? Or is there some specific way to avoid a recursion limit?
推荐答案
递归并不是 Python 中最惯用的处理方式,因为它没有 尾递归 优化,从而使使用递归代替迭代变得不切实际(即使在您的示例中该函数不是尾递归的,无论如何也无济于事).基本上,这意味着如果您希望输入很大,则不应将其用于复杂性大于线性的事物(仍然可以执行具有对数递归深度的事物,例如分治算法作为 QuickSort).
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).
如果您想尝试这种方法,请使用更适合进行函数式编程的语言,例如 Lisp、Scheme、Haskell、OCaml 等;或者尝试使用 Stackless Python,它在堆栈使用方面有更广泛的限制,并且还具有尾递归优化 :-)
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:
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 方法是:
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:
print sum(n for n in xrange(2, 2000001) if all(n % i for i in xrange(2, int(n**0.5)+1)))
(好吧,也许把它分成几行会更像 Pythonic,但我喜欢单行 ^_^)
(OK, maybe splitting it in various lines would be even more Pythonic, but I love one liners ^_^)
这篇关于Python递归函数报错:“超出最大递归深度"的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!