python 递归限制

python不能无限的递归调用下去。并且当输入的值太大，递归次数太多时，python 都会报错

RecursionError: maximum recursion depth exceeded in comparison

首先说结论，python解释器这么会限制递归次数，这么做为了避免"无限"调用导致的堆栈溢出。

tail recursion

tail recursion 就是指在程序最后一步执行递归。这种函数称为 tail recursion function。举个例子：

def fact(n):
    if n == 0:
        return 1

    return n * fact(n-1)

这个函数就是普通的递归函数，它在递归之后又进行了 乘 的操作。 这种普通递归，每一次递归调用都会重新推入一个调用堆栈。
把上述调用改成 tail recursion function

def fact(n, a=1):
    if n == 0:
        return a

    return fact(n - 1, n * a)

tail recursion 的好处是每一次都计算完，将结果传递给下一次调用，然后本次调用任务就结束了，不会参与到下一次的递归调用。这种情况下，只重复用到了一个堆栈。因此可以优化结构。就算是多次循环，也不会出现栈溢出的情况。这就是 tail recursion optimization 。

c和c++都有这种优化， python没有，所以限制了调用次数，就是为了防止无限递归造成的栈溢出。

如果递归次数过多，导致了开头的报错，可以使用 sys 包手动设置recursion的limit

def fact(n):
    if n == 0:
        return 1

    return n * fact(n-1)

if __name__ == '__main__':
    f = int(input('input number: \n'))
    print(fact(f))

# 当你输入100时，正常输出结果. 
# 当你输入1000时。python 会报错： maximum recursion depth exceeded in comparison

手动放大 recursionlimit 限制：

import sys

sys.setrecursionlimit(10**6)

def fact(n):
    if n == 0:
        return 1

    return n * fact(n-1)

if __name__ == '__main__':
    f = int(input('input number: \n'))
    print(fact(f))

# 此时输入1000， 有正常计算结果返回