Python中使用装饰器来优化尾递归的示例
尾递归简介
尾递归是函数返回最后一个操作是递归调用，则该函数是尾递归。
递归是线性的比如factorial函数每一次调用都会创建一个新的栈(last-in-first-out)通过不断的压栈，来创建递归,很容易导致栈的溢出。而尾递归则使用当前栈通过数据覆盖来优化递归函数。
阶乘函数factorial,通过把计算值传递的方法完成了尾递归。但是python不支出编译器优化尾递归所以当递归多次的话还是会报错(学习用)。
eg：
deffactorial(n,x): ifn==0: returnx else: returnfactorial(n-1,n*x) printfactorial(5,1)#120
尾递归优化
这里用到了斐波那契数来作为例子.线性递归的算法由于太过一低效就被我们Pass掉了，我们先来看尾递过方式的调用：
(n,b1=1,b2=1,c=3): ifn<3: return1 else: ifn==c: returnb1+b2 else: returnFib(n,b1=b2,b2=b1+b2,c=c+1)
这段程序我们来测试一下，调用Fib(1001)结果：
>>>defFib(n,b1=1,b2=1,c=3): ...ifn<3: ...return1 ...else: ...ifn==c: ...returnb1+b2 ...else: ...returnFib(n,b1=b2,b2=b1+b2,c=c+1) ... >>>Fib(1001) 70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501L >>>
如果我们用Fib(1002)，结果，茶几了，如下：
..... File"<stdin>",line8,inFib File"<stdin>",line8,inFib File"<stdin>",line8,inFib File"<stdin>",line8,inFib File"<stdin>",line8,inFib File"<stdin>",line8,inFib RuntimeError:maximumrecursiondepthexceeded >>>
好了，现在我们来尾递归优化
我们给刚才的Fib函数增加一个Decorator,如下：
@tail_call_optimized defFib(n,b1=1,b2=1,c=3): ifn<3: return1 else: ifn==c: returnb1+b2 else: returnFib(n,b1=b2,b2=b1+b2,c=c+1)
恩，就是这个@tail_call_optimized的装饰器，这个装饰器使Python神奇的打破了调用栈的限制。
这下即使我们Fib(20000)，也能在780ms跑出结果（780ms是以前博文提到那台2000元的上网本跑出来的结果）
不卖关子了，下面我们来看看这段神奇的代码：
classTailRecurseException: def__init__(self,args,kwargs): self.args=args self.kwargs=kwargs deftail_call_optimized(g): """ Thisfunctiondecoratesafunctionwithtailcall optimization.Itdoesthisbythrowinganexception ifitisit'sowngrandparent,andcatchingsuch exceptionstofakethetailcalloptimization. Thisfunctionfailsifthedecorated functionrecursesinanon-tailcontext. """ deffunc(*args,**kwargs): f=sys._getframe() iff.f_backandf.f_back.f_backandf.f_back.f_back.f_code==f.f_code: raiseTailRecurseException(args,kwargs) else: while1: try: returng(*args,**kwargs) exceptTailRecurseException,e: args=e.args kwargs=e.kwargs func.__doc__=g.__doc__ returnfunc
使用的方法前面已经展示了，令我感到大开眼界的是，作者用了抛出异常然后自己捕获的方式来打破调用栈的增长，简直是太匪夷所思了。而且效率问题，和直接尾递归Fib相比大概造成了五倍的时间开销。
最后很不可思议的，尾递归优化的目的达成了。