彩票走势图

　　一般来说，Python和Java、C#一样，是没有尾递归自动优化的能力的，递归调用受到调用栈长度的限制被广泛的诟病，但本文将给大家一个匪夷所思的方法，来实现Python的尾递归优化，因此Python的递归调用再也不用受到调用栈长度的制约。

　　先来看尾递过方式的调用：

　　defFib(n,b1=1,b2=1,c=3):  

　　ifn<3: 

　　return1  

　　else:

　　ifn==c:

　　returnb1+b2

　　else:

　　returnFib(n,b1=b2,b2=b1+b2,cc=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,cc=c+1)  

　　...  

　　>>>Fib(1001)

　　703303677114228158218352548771835497701812698363587327426

　　049050871545371181969335797422494945626117334877504492417  

　　659910881863632654502236471060120533741212738673391111981 &nbsp;

　　39373125598767690091902245245323403501L 

　　如果我们用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,cc=c+1)

　　就是这个@tail_call_optimized的装饰器，这个装饰器使Python神奇的打破了调用栈的限制。这下即使我们Fib(20000)，也能在780ms跑出结果。

　　importsys

　　classTailRecurseException:

　　def__init__(self,args,kwargs):  

　　self.args=args

　　self.kwargs=kwargs

　　deftail_call_optimized(g):

　　"""

　　Thisfunctiondecoratesafunctionwithtailcall  

　　optimization.Itdoesthisbythrowinganexception  

　　ifitisit'sowngrandparent,andcatchingsuch

　　exceptionstofakethetailcalloptimization.  

　　Thisfunctionfailsifthedecorated  

　　"""

　　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相比大概造成了五倍的时间开销。最后很不可思议的，尾递归优化的目的达成了。