Python 中的最大递归深度是多少，如何增加它？

What is the maximum recursion depth in Python, and how to increase it?

提问by quantumSoup

I have this tail recursive function here:

我在这里有这个尾递归函数：

def recursive_function(n, sum):
    if n < 1:
        return sum
    else:
        return recursive_function(n-1, sum+n)

c = 998
print(recursive_function(c, 0))

It works up to n=997, then it just breaks and spits out a RecursionError: maximum recursion depth exceeded in comparison. Is this just a stack overflow? Is there a way to get around it?

它可以工作n=997，然后它就会中断并吐出一个RecursionError: maximum recursion depth exceeded in comparison. 这只是堆栈溢出吗？有没有办法绕过它？

采纳答案by Thomas Wouters

It is a guard against a stack overflow, yes. Python (or rather, the CPython implementation) doesn't optimize tail recursion, and unbridled recursion causes stack overflows. You can check the recursion limit with sys.getrecursionlimitand change the recursion limit with sys.setrecursionlimit, but doing so is dangerous -- the standard limit is a little conservative, but Python stackframes can be quite big.

是的，它可以防止堆栈溢出。Python（或者更确切地说，CPython 实现）不会优化尾递归，并且无节制的递归会导致堆栈溢出。您可以使用 来检查递归限制sys.getrecursionlimit并使用 更改递归限制sys.setrecursionlimit，但这样做很危险——标准限制有点保守，但 Python 堆栈帧可能非常大。

Python isn't a functional language and tail recursion is not a particularly efficient technique. Rewriting the algorithm iteratively, if possible, is generally a better idea.

Python 不是函数式语言，尾递归也不是特别有效的技术。如果可能，迭代地重写算法通常是一个更好的主意。

回答by David Young

Looks like you just need to set a higher recursion depth:

看起来你只需要设置一个更高的递归深度：

import sys
sys.setrecursionlimit(1500)

回答by Scharron

It's to avoid a stack overflow. The Python interpreter limits the depths of recursion to help you avoid infinite recursions, resulting in stack overflows. Try increasing the recursion limit (sys.setrecursionlimit) or re-writing your code without recursion.

这是为了避免堆栈溢出。Python 解释器限制了递归的深度，以帮助您避免无限递归，从而导致堆栈溢出。尝试增加递归限制 ( sys.setrecursionlimit) 或在不递归的情况下重新编写代码。

From the Python documentation:

从Python 文档：

sys.getrecursionlimit()

Return the current value of the recursion limit, the maximum depth of the Python interpreter stack. This limit prevents infinite recursion from causing an overflow of the C stack and crashing Python. It can be set by setrecursionlimit().

sys.getrecursionlimit()

返回递归限制的当前值，Python解释器堆栈的最大深度。此限制可防止无限递归导致 C 堆栈溢出和 Python 崩溃。它可以由 设置setrecursionlimit()。

回答by Marcelo Cantos

Use a language that guarantees tail-call optimisation. Or use iteration. Alternatively, get cute with decorators.

使用保证尾调用优化的语言。或者使用迭代。或者，使用装饰器变得可爱。

回答by Daniel

I realize this is an old question but for those reading, I would recommend against using recursion for problems such as this - lists are much faster and avoid recursion entirely. I would implement this as:

我意识到这是一个老问题，但对于那些阅读者，我建议不要对此类问题使用递归 - 列表要快得多，并且完全避免递归。我会将其实现为：

def fibonacci(n):
    f = [0,1,1]
    for i in xrange(3,n):
        f.append(f[i-1] + f[i-2])
    return 'The %.0fth fibonacci number is: %.0f' % (n,f[-1])

(Use n+1 in xrange if you start counting your fibonacci sequence from 0 instead of 1.)

（如果您从 0 而不是 1 开始计算您的斐波那契数列，请在 xrange 中使用 n+1。）

回答by Tyler

I had a similar issue with the error "Max recursion depth exceeded". I discovered the error was being triggered by a corrupt file in the directory I was looping over with os.walk. If you have trouble solving this issue and you are working with file paths, be sure to narrow it down, as it might be a corrupt file.

我遇到了类似的错误“超出最大递归深度”的问题。我发现错误是由我正在循环的目录中的损坏文件触发的os.walk。如果您在解决此问题时遇到问题并且正在处理文件路径，请务必缩小范围，因为它可能是一个损坏的文件。

回答by alex

Use generators?

使用发电机？

def fib():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

fibs = fib() #seems to be the only way to get the following line to work is to
             #assign the infinite generator to a variable

f = [fibs.next() for x in xrange(1001)]

for num in f:
        print num

above fib() function adapted from: http://intermediatepythonista.com/python-generators

以上 fib() 函数改编自：http: //intermediatepythonista.com/python-generators

回答by rwst

Of course Fibonacci numbers can be computed in O(n) by applying the Binet formula:

当然，斐波那契数可以通过应用比奈公式在 O(n) 中计算：

from math import floor, sqrt

def fib(n):                                                     
    return int(floor(((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))+0.5))

As the commenters note it's not O(1) but O(n) because of 2**n. Also a difference is that you only get one value, while with recursion you get all values of Fibonacci(n)up to that value.

正如评论者所指出的，它不是 O(1) 而是 O(n) 因为2**n。还有一个区别是您只能获得一个值，而通过递归，您可以获得该值以内的所有值Fibonacci(n)。

回答by Harun ERGUL

Many recommend that increasing recursion limit is a good solution however it is not because there will be always limit. Instead use an iterative solution.

许多人建议增加递归限制是一个很好的解决方案，但这不是因为总会有限制。而是使用迭代解决方案。

def fib(n):
    a,b = 1,1
    for i in range(n-1):
        a,b = b,a+b
    return a
print fib(5)

回答by martineau

As @alex suggested, you could use a generator function to do this sequentially instead of recursively.

正如@alex建议的那样，您可以使用生成器函数按顺序执行此操作，而不是递归执行。

Here's the equivalent of the code in your question:

这是您问题中的代码的等价物：

def fib(n):
    def fibseq(n):
        """ Iteratively return the first n Fibonacci numbers, starting from 0. """
        a, b = 0, 1
        for _ in xrange(n):
            yield a
            a, b = b, a + b

    return sum(v for v in fibseq(n))

print format(fib(100000), ',d')  # -> no recursion depth error