匪夷所思 Python实现尾递归优化

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

51CTO推荐阅读：使用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  


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  


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