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

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。这是因为栈溢出吗？有没有办法解决这个问题？

Answer 1

如果你经常需要改变递归的限制（比如在解决编程难题的时候），你可以像下面这样定义一个简单的上下文管理器：

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这个命令或者limits.conf(5)文件来实现这一点。

Answer 2

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

import sys
sys.setrecursionlimit(1500)

Answer 3

这是为了防止栈溢出，没错。Python（更准确地说，是CPython这个实现）并不会优化尾递归，而无限制的递归会导致栈溢出。你可以用 sys.getrecursionlimit 来查看当前的递归限制：

import sys
print(sys.getrecursionlimit())

你也可以用 sys.setrecursionlimit 来改变递归限制：

sys.setrecursionlimit(1500)

不过这样做是有风险的——标准限制设置得比较保守，但Python的栈帧可能会很大。

Python并不是一种函数式编程语言，尾递归并不是一种特别高效的技巧。如果可以的话，重新用迭代的方式来写算法通常是更好的选择。