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

一般来说，Python和Java、C#一样，是没有尾递归自动优化的能力的，递归调用受到调用栈长度的限制被广泛的诟病，但本文将给大家一个匪夷所思的方法，来实现Python的尾递归优化，因此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  
  
  
  39373125598767690091902245245323403501L

如果我们用Fib(1002)，结果如下：

 
 
 
  
  
  .....  
  
  
  File"",line8,inFib  
  
  
  File"",line8,inFib  
  
  
  File"",line8,inFib  
  
  
  File"",line8,inFib  
  
  
  File"",line8,inFib  
  
  
  File"",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

使用的方法前面已经展示了，作者用了抛出异常然后自己捕获的方式来打破调用栈的增长，简直是太匪夷所思了。而且效率问题，和直接尾递归Fib相比大概造成了五倍的时间开销。最后很不可思议的，尾递归优化的目的达成了。

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

【编辑推荐】

Python闭包的概念、形式与应用
Python自动单元测试框架的应用详解
旁观者清 Python与Ruby各有千秋
手把手教您Python多线程应用技巧
加速程序开发 Python整合C语言模块

标题名称：匪夷所思Python实现尾递归优化
浏览地址：http://cdxtjz.cn/article/dpdhjpj.html

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

其他资讯