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

2024-03-29 00:33:39 发布

您现在位置:Python中文网/ 问答频道 /正文

我用下面的代码解决了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. is prime检查数字是否为素数
  2. prime list返回一个列表,该列表包含一组限定为“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给了我:

运行时错误:超过最大递归深度

我的递归函数做错了什么?或者有什么特定的方法来避免递归限制?


Tags: 函数代码in列表forreturnifdef
3条回答

如前所述,在不能处理深层堆栈的语言中,最好采用迭代方法。尤其是在您的情况下,最好更改使用的算法。我建议使用Sieve of Eratosthenes来查找素数列表。它会比你现在的程序快得多。

递归并不是Python中最惯用的方法,因为它没有tail recursion优化,因此使用递归代替迭代是不切实际的(即使在您的示例中,函数不是tail recursive,这也没有帮助)。基本上,这意味着如果你期望你的输入是大的,那么你不应该使用它来处理复杂度大于线性的事情(对于那些具有对数递归深度的事情还是可以的,比如分而治之的快速排序算法)。

如果您想尝试这种方法,请使用一种更适合于函数式编程的语言,如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 []))

另一个“顺便说一句”,如果你只是用它来累加值,就不应该构造一个列表。。。解决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)))

(好吧,也许把它分成几行会更像Python,但我喜欢一行)

我不是python专家,但我想你已经达到了stack的极限。这就是递归的问题,当你不需要递归很多次的时候它是很好的,但是当递归的数量变得稍微大一些的时候就不好了。

理想的替代方法是重写算法以使用迭代。

编辑:实际上,仔细查看了您的特定错误后,您可以通过更改sys.getrecursionlimit来克服它。不过,这只能带你走这么远。最后你会得到一个stackoverflow异常,这使我回到了我原来的观点。

相关问题 更多 >