日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

一般來說，Python和Java、C#一樣，是沒有尾遞歸自動優(yōu)化的能力的，遞歸調(diào)用受到調(diào)用棧長度的限制被廣泛的詬病，但本文將給大家一個匪夷所思的方法，來實現(xiàn)Python的尾遞歸優(yōu)化，因此Python的遞歸調(diào)用再也不用受到調(diào)用棧長度的制約。

推薦閱讀：使用Python遞歸對文件進行相關(guān)處理

先來看尾遞過方式的調(diào)用：

 
 
 

  
  
  
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) 
 
 
 

這段程序我們來測試一下，調(diào)用Fib(1001)結(jié)果：

 
 
 

  
  
  
>>>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)，結(jié)果如下：

 
 
 

  
  
  
.....  
  
  
  
File"",line8,inFib  
  
  
  
File"",line8,inFib  
  
  
  
File"",line8,inFib  
  
  
  
File"",line8,inFib  
  
  
  
File"",line8,inFib  
  
  
  
File"",line8,inFib  
  
  
  
RuntimeError:maximumrecursiondepthexceeded 
 
 
 

現(xiàn)在我們來尾遞歸優(yōu)化。我們給剛才的Fib函數(shù)增加一個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神奇的打破了調(diào)用棧的限制。這下即使我們Fib(20000)，也能在780ms跑出結(jié)果。

 
 
 

  
  
  
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 
 
 
 

使用的方法前面已經(jīng)展示了，作者用了拋出異常然后自己捕獲的方式來打破調(diào)用棧的增長，簡直是太匪夷所思了。而且效率問題，和直接尾遞歸Fib相比大概造成了五倍的時間開銷。最后很不可思議的，尾遞歸優(yōu)化的目的達成了。

原文鏈接：http://www.cnblogs.com/Alexander-Lee/archive/2010/09/16/1827587.html

【編輯推薦】

1. Python閉包的概念、形式與應(yīng)用
2. Python自動單元測試框架的應(yīng)用詳解
3. 旁觀者清 Python與Ruby各有千秋
4. 手把手教您Python多線程應(yīng)用技巧
5. 加速程序開發(fā) Python整合C語言模塊

網(wǎng)站標(biāo)題：匪夷所思Python實現(xiàn)尾遞歸優(yōu)化
文章起源：http://www.5511xx.com/article/dpdhjpj.html