首页 文章

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

提问于
浏览 次
254

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

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

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

它可以达到n = 997，然后它就会中断并吐出"maximum recursion depth exceeded in comparison" RuntimeError . 这只是一个堆栈溢出？有办法解决它吗？

python recursion

13 回答

  • 1

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

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

    回复于
  • 33

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

    sys.setrecursionlimit(1500)
    回复于
  • 10

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

    来自python website：

    sys.getrecursionlimit（）返回递归限制的当前值，即Python解释器堆栈的最大深度 . 此限制可防止无限递归导致C堆栈溢出并导致Python崩溃 . 它可以通过setrecursionlimit（）设置 .

    回复于
  • 10

    使用保证尾调用优化的语言 . 或者使用迭代 . 或者，decorators变得可爱 .

    回复于
  • 3

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

    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])

    （如果从0开始计算斐波那契数列而不是1，则在xrange中使用n 1 . ）

    回复于
  • 3

    当然，通过应用Binet公式，可以在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))

    由于评论者注意到它不是O（1）而是O（n）因为 2**n . 另外一个区别是你只获得一个值，而使用递归，你得到 Fibonacci(n) 的所有值都达到该值 .

    回复于
  • 7

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

    回复于
  • 79

    resource.setrlimit must also be used to increase the stack size and prevent segfault

    Linux内核限制了进程堆栈 .

    Python将局部变量存储在解释器的堆栈中，因此递归占用了解释器的堆栈空间 .

    如果Python解释器试图超过堆栈限制，Linux内核会对其进行分段 .

    堆栈限制大小由 getrlimit 和 setrlimit 系统调用控制 .

    Python通过 resource 模块提供对这些系统调用的访问 .

    import resource
import sys

print resource.getrlimit(resource.RLIMIT_STACK)
print sys.getrecursionlimit()
print

# Will segfault without this line.
resource.setrlimit(resource.RLIMIT_STACK, [0x10000000, resource.RLIM_INFINITY])
sys.setrecursionlimit(0x100000)

def f(i):
    print i
    sys.stdout.flush()
    f(i + 1)
f(0)

    当然，如果你继续增加ulimit，你的RAM将耗尽，这将使你的计算机因交换疯狂而停止运行，或者通过OOM杀手杀死Python .

    从bash中，您可以看到并设置堆栈限制（以kb为单位）：

    ulimit -s
ulimit -s 10000

    我的默认值是8Mb .

    也可以看看：

    在Ubuntu 16.10，Python 2.7.12上测试过 .

    回复于
  • 295

    使用发电机？

    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

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

    回复于
  • 5

    如果您经常需要更改递归限制（例如在解决编程难题时），您可以像这样定义一个简单的context manager：

    import sys

class recursionlimit:
    def __init__(self, limit):
        self.limit = limit
        self.old_limit = sys.getrecursionlimit()

    def __enter__(self):
        sys.setrecursionlimit(self.limit)

    def __exit__(self, type, value, tb):
        sys.setrecursionlimit(self.old_limit)

    然后调用具有自定义限制的函数，您可以执行以下操作：

    with recursionlimit(1500):
    print(fib(1000, 0))

    退出 with 语句的主体时，递归限制将恢复为默认值 .

    回复于
  • 2

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

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

    如果您只想获得少量Fibonacci数，则可以使用矩阵方法 .

    from numpy import matrix

def fib(n):
    return (matrix('0 1; 1 1', dtype='object') ** n).item(1)

    numpy使用快速取幂算法很快 . 你在O（log n）得到答案 . 它比Binet的公式更好，因为它只使用整数 . 但是如果你想要所有斐波纳契数都达到n，那么最好通过记忆来做到这一点 .

    回复于
  • 16

    作为@alex suggested，您可以使用生成器函数来执行此操作 . 这是您问题中代码的等价物：

    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
    回复于

相关问题