Python中使用装饰器来优化尾递归的示例

yipeiwu_com7年前Python基础

尾递归简介
尾递归是函数返回最后一个操作是递归调用,则该函数是尾递归。
递归是线性的比如factorial函数每一次调用都会创建一个新的栈(last-in-first-out)通过不断的压栈,来创建递归, 很容易导致栈的溢出。而尾递归则使用当前栈通过数据覆盖来优化递归函数。
阶乘函数factorial, 通过把计算值传递的方法完成了尾递归。但是python不支出编译器优化尾递归所以当递归多次的话还是会报错(学习用)。

eg:

def factorial(n, x):
  if n == 0:
    return x
  else:
    return factorial(n-1, n*x)

print factorial(5, 1) # 120

尾递归优化
这里用到了斐波那契数来作为例子.线性递归的算法由于太过一低效就被我们Pass掉了,我们先来看尾递过方式的调用:

(n,b1=1,b2=1,c=3):
 if n<3:
  return 1
 else:
  if n==c:
   return b1+b2
  else:
   return Fib(n,b1=b2,b2=b1+b2,c=c+1)

这段程序我们来测试一下,调用 Fib(1001)结果:

>>> def Fib(n,b1=1,b2=1,c=3):

...  if n<3:

...   return 1

...  else:

...   if n==c:

...    return b1+b2

...   else:

...    return Fib(n,b1=b2,b2=b1+b2,c=c+1)

... 

>>> Fib(1001)

70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501L

>>> 

如果我们用Fib(1002),结果,茶几了,如下:

 .....

 File "<stdin>", line 8, in Fib

 File "<stdin>", line 8, in Fib

 File "<stdin>", line 8, in Fib

 File "<stdin>", line 8, in Fib

 File "<stdin>", line 8, in Fib

 File "<stdin>", line 8, in Fib

RuntimeError: maximum recursion depth exceeded

>>> 

好了,现在我们来尾递归优化

我们给刚才的Fib函数增加一个Decorator,如下:

@tail_call_optimized
def Fib(n,b1=1,b2=1,c=3):
 if n<3:
  return 1
 else:
  if n==c:
   return b1+b2
  else:
   return Fib(n,b1=b2,b2=b1+b2,c=c+1)

 
恩,就是这个@tail_call_optimized的装饰器 ,这个装饰器使Python神奇的打破了调用栈的限制。

这下即使我们Fib(20000),也能在780ms跑出结果(780ms是以前博文提到那台2000元的上网本跑出来的结果)

不卖关子了,下面我们来看看这段神奇的代码: 

class TailRecurseException: 
 def __init__(self, args, kwargs): 
 self.args = args 
 self.kwargs = kwargs 
 
def tail_call_optimized(g): 
 """ 
 This function decorates a function with tail call 
 optimization. It does this by throwing an exception 
 if it is it's own grandparent, and catching such 
 exceptions to fake the tail call optimization. 
 
 This function fails if the decorated 
 function recurses in a non-tail context. 
 """ 
 def func(*args, **kwargs): 
 f = sys._getframe() 
 if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code: 
  raise TailRecurseException(args, kwargs) 
 else: 
  while 1: 
  try: 
   return g(*args, **kwargs) 
  except TailRecurseException, e: 
   args = e.args 
   kwargs = e.kwargs 
 func.__doc__ = g.__doc__ 
 return func

使用的方法前面已经展示了,令我感到大开眼界的是,作者用了抛出异常然后自己捕获的方式来打破调用栈的增长,简直是太匪夷所思了。而且效率问题,和直接尾递归Fib相比大概造成了五倍的时间开销。

最后很不可思议的,尾递归优化的目的达成了。

相关文章

django批量导入xml数据

django后台批量导入数据 在生产环境中,往往数据不是几条或者几百条,那么举个例子,将公司所有员工员工号或者帐号密码导入进后台,那就不建议你去后台一条条记录去添加了 如何从xml中批...

Python考拉兹猜想输出序列代码实践

考拉兹猜想(英语:Collatz conjecture),是指对于每一个正整数,如果它是奇数,则对它乘3再加1,如果它是偶数,则对它除以2,如此循环,最终都能够得到1。(摘自Wiki)...

在IPython中执行Python程序文件的示例

简单使用了一下之后,我觉得如果有机会(公司里面编码是极不自由的,也无所谓,我在公司不做数据分析),我肯定是更喜欢使用IPython作为我的Python shell环境了。简单的接触发现了...

Python多重继承的方法解析执行顺序实例分析

Python多重继承的方法解析执行顺序实例分析

本文实例讲述了Python多重继承的方法解析执行顺序。分享给大家供大家参考,具体如下: 任何实现多重继承的语言都要处理潜在的命名冲突, 这种冲突由不相关的祖先类实现同名方法引起 c...

python 字典 setdefault()和get()方法比较详解

python 字典 setdefault()和get()方法比较详解

dict.setdefault(key, default=None) --> 有key获取值,否则设置 key:default,并返回default,default默认值为None...