尾递归思考

概念

递归是函数不停的调用自身直到满足结束条件退出。递归存在一个很大的问题就是随着递归的深入，占用大量的栈空间，最后很有可能导致栈溢出。
尾递归是递归的一种特例。尾递归从名字上理解就是把递归放到函数的最后。在尾递归中，先执行计算的部分，然后把计算结果，作为参数传入下一次递归。

实例

众所周知斐波那契数列是递归的一个例子。

递归实现

def fibonacci(n):
    if n <= 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

当我们调用fibonacci(1001)的时候，会抛出下面的异常：

RecursionError: maximum recursion depth exceeded in comparison

从异常看已经超出了递归调用的最大深度，系统的最大深度可以通过sys.getrecursionlimit()获得，这个设置的默认值是1000。当然我们可以修改这个值达到我们的要求。

尾递归实现

def fibonacci(n, b1=1, b2=1, c=3):
    if n < 3:
        return 1
    else:
        if n == c:
            return b1 + b2
        else:
            return fibonacci(n, b1=b2, b2=b1+b2, c=c+1)

尾递归的特点就是最后返回的结果就是下次调用返回的结果。
同样我们也调用fibonacci(1001)，很遗憾还是抛出了异常：

RecursionError: maximum recursion depth exceeded in comparison

这说明了python没有对尾递归做任何的优化。对于尾递归来说每次调用的函数除了参数的数值不一样，其他完全一样，也就是说完全可以仅仅修改一下参数的数值利用栈内保存的函数就能处理。

神奇的装饰器

既然没有优化，那就没有其他办法了吗？当然是有的，这里不得不提一下一个神奇的装饰器@tail_call_optimized。(参照：http://code.activestate.com/recipes/474088/)

import sys


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


def tail_call_optimized(g):
    """
    This function decorates a function with tail call
    optimization. It does this by throwing an exception
    if it is it's own grandparent, and catching such
    exceptions to fake the tail call optimization.

    This function fails if the decorated
    function recurses in a non-tail context.
    """

    def func(*args, **kwargs):
        f = sys._getframe()
        if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code:
            raise TailRecurseException(args, kwargs)
        else:
            while 1:
                try:
                    return g(*args, **kwargs)
                except TailRecurseException as e:
                    args = e.args
                    kwargs = e.kwargs

    func.__doc__ = g.__doc__
    return func

这个装饰器实现的原理确实精妙，当进行第二次调用的时候就抛出一个异常，把参数修改一下，然后返回调用。这样就保证了不会有大量的函数堆积在栈里面。
然后把刚才的尾递归修改一下：

@tail_call_optimized
def fib(n, b1=1, b2=1, c=3):
    if n < 3:
        return 1
    else:
        if n == c:
            return b1 + b2
        else:
            return fib(n, b1=b2, b2=b1+b2, c=c+1)

然后再调用一下fibonacci(1001)，没有异常了。

70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501

其他相关

其实对于一些语言是存在尾递归优化的，比如C语言编译的时候加优化参数 -O2就可以实现。