尾递归

1. 栈的深度限制

通过上一篇《函数的调用过程》，你现在已经知道函数调用执行过程中要使用到栈这种数据结构。关于存储函数调用信息的栈，你要知道一点，它的深度是有限制的，也就是说，你不能无限制的向里面放函数的信息，大多数时候，栈的深度可以满足我们的日常要求，但是如果碰上递归就不好说了，递归的过程就是函数调用自身，具体调用多少次，取决于算法，咱们以简单的斐波那契数列为例

import sys
def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)


print(sys.getrecursionlimit())
print(fib(10000))

sys.getrecursionlimit() 返回的是python中对栈的深度限制，执行这段代码，很快就会报错

RecursionError: maximum recursion depth exceeded in comparison

由于递归的次数太多了，所以超出了栈的深度限制

2. 尾递归

如果递归调用是子过程的最后一步，那么就是尾递归，上面的代码不是尾递归，因为计算fib(n)总是要先得到fib(n-1)和fib(n-2)，下面的代码是一个尾递归

def tail_fib(n, a, b):
    if n == 1:
        return a
    else:
        return tail_fib(n-1, b, a+b)

print(fib(8))
print(tail_fib(9, 0, 1))

3. 利用尾递归突破栈深度限制

函数调用过程中，相关信息都保存在了栈中，对于尾递归同样如此，但是对于尾递归来说，每一次调用自身时，之前保存的那些信息都没有使用价值了，道理就在于tail_fib执行结束之后，直接return了，根本不需要回到上一次调用它的函数中继续执行什么，所以先前放入栈中的信息都是没有价值的，那么如果能利用那些旧的栈空间，就可以在不增加栈的深度的情况下放入新的函数调用信息。

下面的代码是从一篇文章借鉴而来，遗憾的是这个网址已经无法访问了，为表示对原作者的尊重，仍既然将地址放在这里

http://cyrusin.github.io/2015/12/08/python-20151208/

import sys


class TailCallException(BaseException):
    def __init__(self, args, kwargs):
        self.args = args
        self.kwargs = kwargs


def tail_call_optimized(func):
    def _wrapper(*args, **kwargs):
        f = sys._getframe()
        # 当前帧的代码和当前帧的前一个帧的前一个帧的代码相同，此时，有三个帧
        if f.f_back and f.f_back.f_back and f.f_code == f.f_back.f_back.f_code:
            raise TailCallException(args, kwargs)  # 抛出异常
        else:
            while True:
                try:
                    return func(*args, **kwargs)
                except TailCallException as e:
                    # 这里捕获到异常，同时，也得到了函数执行时的参数，args和 kwargs
                    # 抛出异常的函数退出了，那么它的帧也就被回收了
                    args = e.args
                    kwargs = e.kwargs
    return _wrapper


@tail_call_optimized
def tail_fib(n, a, b):
    if n == 1:
        return a
    else:
        return tail_fib(n-1, b, a+b)


print(tail_fib(100005, 0, 1))

通过sys._getframe()获得了函数的帧栈信息，如果当前帧的代码和前一个帧的前一个帧的代码相同，就说明递归调用已经发生了2次，那么此时就抛出一个异常。

这里有一个很关键的点要搞清楚，当我们执行tail_fib(100005, 0, 1)时，tail_fib是被tail_call_optimized装饰过的函数，当执行return func(*args, **kwargs)时，所执行的是没有被装饰过的函数，而在函数内部调用return tail_fib(n-1, b, a+b)时，tail_fib是被装饰过的函数。

整个执行过程如下：

执行tail_fib(100005, 0, 1)
判断f.f_code == f.f_back.f_back.f_code，不抛异常
执行return func(*args,**kwargs)，进入函数tail_fib
执行return tail_fib(n-1, b, a+b)，进入被装饰后的函数
判断f.f_code == f.f_back.f_back.f_code 抛异常
捕获异常，得到参数，执行return func(*args, **kwargs)，进入函数tail_fib
执行return tail_fib(n-1, b, a+b)，注意a+b，每次都进行了计算
判断f.f_code == f.f_back.f_back.f_code，抛异常

重复6， 7， 8 三个步骤。