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

Question

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

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

它在 n=997 之前都能正常工作，然后就会崩溃并输出一个 "RecursionError: maximum recursion depth exceeded in comparison" 的错误。这只是堆栈溢出吗？有没有办法解决这个问题？

- quantumSoup

---

请参见https://dev59.com/6G445IYBdhLWcg3wDWCc。 - Thomas Ahle

记忆化可以通过使先前计算的值终止而不是增加堆栈大小来加速函数并增加其有效递归深度。 - Cyoce

递归深度通常限制在1000。 - user3064538

@tonix 这个解释器会添加一个栈帧（在堆栈跟踪中的 line <n>, in <module>），对于 n=1，这段代码需要 2 个栈帧（因为基本情况是 n < 1，所以对于 n=1 它仍然发生了递归）。我猜测递归深度限制不包括其本身，也就是说，它是“当你达到1000时出错”，而不是“如果你超过1000（1001）就会出错”。997 + 2小于1000，所以可以正常运行，但 998 + 2 则无法运行，因为它达到了限制。 - user3064538

@tonix 不行。recursive_function(997) 是可行的，但在第998次调用时会崩溃。当你调用recursive_function(998)时，它使用了999个堆栈帧，并且解释器会添加1个帧（因为你的代码总是运行在顶级模块中），这使得它达到了1000个限制。 - user3064538

Answer 1

这是对栈溢出的一种保护措施。Python（或者更确切地说CPython实现）不会优化尾递归，无限递归会导致栈溢出。您可以使用 sys.getrecursionlimit 来检查递归限制：

import sys
print(sys.getrecursionlimit())

使用sys.setrecursionlimit更改递归限制：

sys.setrecursionlimit(1500)

然而这样做是危险的--标准限制有点保守，但Python堆栈帧可能非常大。

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

- Thomas Wouters

---

根据我的经验，您需要在sys和resource模块中都增加限制：https://dev59.com/6G445IYBdhLWcg3wDWCc#16248113。 - Thomas Ahle

作为将其转换为迭代版本的策略，可以使用尾递归优化装饰器。 - jfs

您可以使用http://svn.python.org/projects/python/trunk/Tools/scripts/find_recursionlimit.py来查找您的操作系统的最大递归深度限制。 - Ullullu

对于那些对源代码感兴趣的人，Python的默认递归限制为1000 https://hg.python.org/cpython/file/tip/Python/ceval.c#l691，并且可以使用API在https://hg.python.org/cpython/file/tip/Python/sysmodule.c#l643进行更改，该API将新的限制值设置为https://hg.python.org/cpython/file/tip/Python/ceval.c#l703。 - Pramod

尾递归是一种在针对此技术进行了优化的编程语言中非常高效的技巧。对于某些问题，它可能比迭代实现更具表现力。该答案可能意味着“特指Python”，但并未直接说明。 - Peter R

Answer 2

看起来你只需要增加递归深度：

import sys
sys.setrecursionlimit(1500)

- David Young

---

在我的情况下，我忘记在基本情况中添加返回语句，导致程序继续执行超过1000次。Python开始抛出异常，让我感到惊讶，因为我确定它将创建多少个堆栈来运行它。 - vijayraj34

sys.setrecursionlimit(50) 或者设置一个小的值是有用的，如果你的程序进入了递归，并且你不想看到无数页相同的错误信息。在调试（我自己的）糟糕递归代码时，我发现这非常有帮助。 - peawormsworth

请注意，此内容受平台相关限制的影响。 - Soid

Answer 3

如果您经常需要更改递归限制（例如在解决编程谜题时），您可以定义一个简单的上下文管理器，如下所示：

import sys

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

    def __enter__(self):
        self.old_limit = sys.getrecursionlimit()
        sys.setrecursionlimit(self.limit)

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

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

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

执行完with语句后，递归限制将恢复为默认值。

附注：对于递归限制的大值，您可能还希望增加Python进程的堆栈大小。例如，可以通过ulimit shell内置或limits.conf（5）文件来完成。

- Eugene Yarmash

---

你还需要使用resource来提高进程的递归限制。如果不这样做，当你将setrecursionlimit设置得太高并尝试使用新的限制时（在我的笔记本电脑上，大约为8MB堆栈帧，相当于~30,000个堆栈帧与上面的简单函数），会出现分段错误并导致整个Python进程崩溃。 - user3064538

@Boris：这可以添加到上下文管理器中，但是提高堆栈大小限制只对root（超级用户）有效。 - Eugene Yarmash

Answer 4

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

来自Python文档：

sys.getrecursionlimit()

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

- Scharron

---

在我的Anaconda x64，Windows上的3.5 Python中，默认限制是1000。 - Guillaume Chevalier

Answer 5

resource.setrlimit必须用于增加堆栈大小，防止段错误。

Linux内核限制进程的堆栈。

Python将本地变量存储在解释器的堆栈上，因此递归占用解释器的堆栈空间。

如果Python解释器尝试超过堆栈限制，则Linux内核会使其出现段错误。

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

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

sys.setrecursionlimit在https://dev59.com/X3A75IYBdhLWcg3wYYBQ#3323013中提到，仅增加Python解释器自身对堆栈大小的限制，但不触及Linux内核对Python进程施加的限制。

示例程序：

main.py

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)

当然，如果你继续增加setrlimit，你的RAM最终会耗尽，这将导致由于交换机制失控而使计算机减速或通过OOM Killer杀死Python。

从bash中，可以使用以下命令查看和设置堆栈限制（以kb为单位）：

ulimit -s
ulimit -s 10000

对我而言，默认值为8Mb。

另请参见：

• 在Python脚本中设置堆栈大小
• Linux、Mac和Windows的硬递归限制是多少？

在Ubuntu 16.10、Python 2.7.12上进行了测试。

- Ciro Santilli OurBigBook.com

---

尝试在Stack Clash修复后设置'rlimit_stack'可能会导致失败或相关问题。另请参见Red Hat的Issue 1463241。 - jww

我使用了这个（Python资源部分）来帮助我在Tim Roughgarden教授的均值（巨大）数据集上实现Kosaraju算法。我的实现在小数据集上运行良好，但对于大型数据集，递归/栈限制是一个问题...或者说不是吗？嗯，是的！谢谢！ - nilo

感谢Ciro提供如此详细的答案！ - X0-user-0X

Answer 6

我知道这是一个老问题，但对于那些正在阅读的人，我建议不要使用递归来解决这类问题-列表更快，而且完全避免了递归。我的实现方式如下：

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开始计算斐波那契数列，请在xrange中使用n+1。)

- Daniel

---

何必使用O(n)的空间，当你可以使用O(1)的空间呢？ - Janus Troelsen

如果O(n)空间的评论让您感到困惑：不要使用列表。列表将保留所有值，而您只需要第n个值。一个简单的算法是保留最后两个斐波那契数并将它们相加，直到得到您需要的数。还有更好的算法。 - Milimetric

在Python 3中，xrange被简称为range。 - Eric O. Lebigot

@EOL 我知道这个。 - Mathime

@Mathime 我是为了让阅读评论的人更明确而进行详细说明。 - Eric O. Lebigot

关于O(1)：可以通过对角化使用矩阵幂来获取第n个斐波那契数，而无需计算所有先前的数。请参见此处的第2页和第3页。 - Martin Ueding

Answer 7

我曾遇到过“超出最大递归深度”错误的类似问题。我发现这个错误是由于正在使用 os.walk 循环遍历的目录中存在损坏的文件所触发的。如果你在处理文件路径时遇到此问题并且无法解决，请确保缩小范围，因为它可能是一个损坏的文件。

- Tyler

---

楼主提供了他的代码，他的实验可以随时再现。这不涉及损坏的文件。 - T. Verron

你说得对，但我的回答并不针对原帖，因为那是四年前的事情了。我的回答旨在帮助由于损坏文件而间接导致 MRD 错误的人们 - 因为这是第一篇搜索结果之一。它帮助到了某些人，因为被点赞了。感谢你的踩。 - Tyler

在搜索我的问题时，我发现这是唯一将“最大递归深度”回溯与损坏文件联系起来的内容。谢谢！ - Jeff

Answer 8

使用支持尾调用优化的编程语言，或者使用迭代。另外，可以通过装饰器来实现。

- Marcelo Cantos

---

这有点儿弃子投水的意思。 - Russell Borogove

@Russell: 我所提供的选项中只有一个建议这样做。 - Marcelo Cantos

“Get cute with decorators” 不是一个选项。 - Mr. B

@Mr.B，除非您需要超过ulimit -s的堆栈帧，否则是这样的https://dev59.com/X3A75IYBdhLWcg3wYYBQ#50120316 - user3064538

Answer 9

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

评论者指出，由于 2 ** n 的存在，它的时间复杂度不是 O(1)，而是 O(n)。此外，与递归不同的是，使用循环只能得到一个值，而使用递归可以得到 Fibonacci(n) 值中所有小于该值的值。

- rwst

---

Python中的long类型没有最大值限制。 - pppery

值得注意的是，由于浮点数精度问题，当n变大时这种方法会失败——在(1+sqrt(5))**n和(1+sqrt(5))**(n+1)之间的差异小于1 ulp，因此您开始得到错误的结果。 - user2508324

NumPy 中实际上没有大整数... - Eric O. Lebigot

@user202729 这并不正确，使用平方法进行指数运算 2**n 的时间复杂度实际上是O(log(n))。具体请参考 Exponentiation by squaring。 - Sam

@user202729 除非以一进制表示，否则任何数字的位数都是O(log(n))。例如，在二进制中，“1”有1位数字，“1,000,000”有10位数字。 - Sam

Answer 10

如果你只想获取几个斐波那契数列的数字，可以使用矩阵方法。

from numpy import matrix

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

由于numpy使用快速指数算法，因此它很快。您可以在O(log n)时间内得到答案。与Binet公式相比，它更好，因为它仅使用整数。但是，如果您想要所有斐波那契数列的值直到n，则最好通过记忆化来实现。

- bebidek

---

很遗憾，在大多数竞赛编程评测中，您无法使用numpy。但是，先生，您的解决方案是我最喜欢的。我已经在一些问题中使用了矩阵解决方案。当您需要一个非常大的斐波那契数并且无法使用模数时，这是最好的解决方案。如果允许使用模数，则Pisano周期是更好的方法。 - mentatkgs