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相比大概造成了五倍的时间开销。

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

赞 (0)

相关推荐

  • 深入学习Python中的装饰器使用

    装饰器 vs 装饰器模式 首先,大家需要明白的是使用装饰器这个词可能会有不少让大家担忧的地方,因为它很容易和设计模式这本书里面的装饰器模式发生混淆.曾经一度考虑给这个新的功能取一些其它的术语名称,但是装饰器最终还是胜出了. 的确,你可以使用python装饰器来实现装饰器模式,但这绝对是它很小的一部分功能,有点暴殄天物.对于python装饰器,我觉得它是最接近宏的存在. 宏的历史 宏有有着非常悠久的历史,不过大多数人可能会有使用C语言预处理宏的经验.但是,对于C语言里的宏来说,它存在一些问题,(1

  • Python的装饰器用法学习笔记

    在python中常看到在定义函数是使用@func. 这就是装饰器, 装饰器是把一个函数作为参数的函数,常常用于扩展已有函数,即不改变当前函数状态下增加功能. def run(): print "I'm run." 我有这么一个函数, 我想知道这个函数什么时候开始什么时候结束. 我应该这么写 def run(): print time.ctime() print "I'm run." print time.ctime() 但是如果不允许修改函数的话就需要装饰器了 de

  • 深入理解Python中装饰器的用法

    因为函数或类都是对象,它们也能被四处传递.它们又是可变对象,可以被更改.在函数或类对象创建后但绑定到名字前更改之的行为为装饰(decorator). "装饰器"后隐藏了两种意思--一是函数起了装饰作用,例如,执行真正的工作,另一个是依附于装饰器语法的表达式,例如,at符号和装饰函数的名称. 函数可以通过函数装饰器语法装饰: @decorator # ② def function(): # ① pass 函数以标准方式定义.① 以@做为定义为装饰器函数前缀的表达式②.在 @ 后的部分必须

  • python中函数总结之装饰器闭包详解

    1.前言 函数也是一个对象,从而可以增加属性,使用句点来表示属性. 如果内部函数的定义包含了在外部函数中定义的对象的引用(外部对象可以是在外部函数之外),那么内部函数被称之为闭包. 2.装饰器 装饰器就是包装原来的函数,从而在不需要修改原来代码的基础之上,可以做更多的事情. 装饰器语法如下: @deco2 @deco1 def func(arg1,arg2...): pass 这个表示了有两个装饰器的函数,那么表示的含义为:func = deco2(deco1(func)) 无参装饰器语法如下:

  • 实例讲解Python编程中@property装饰器的用法

    取值和赋值 class Actress(): def __init__(self): self.name = 'TianXin' self.age = 5 类Actress中有两个成员变量name和age.在外部对类的成员变量的操作,主要包括取值和赋值.简单的取值操作是x=object.var,简单的赋值操作是object.var=value. >>> actress = Actress() >>> actress.name #取值操作 'TianXin' >&g

  • python装饰器初探(推荐)

    一.含有一个装饰器 #encoding: utf-8 ############含有一个装饰器######### def outer(func): def inner(*args, **kwargs):#要装饰f1(),这里用这俩形式参数,可以接受任意个参数,不管f1定义几个参数 print "1" r = func(*args, **kwargs)#这里要用func,不要用f1 print "2" return r return inner @outer #这里ou

  • Python编程中装饰器的使用示例解析

    装饰函数和方法 我们先定义两个简单的数学函数,一个用来计算平方和,一个用来计算平方差: # get square sum def square_sum(a, b): return a**2 + b**2 # get square diff def square_diff(a, b): return a**2 - b**2 print(square_sum(3, 4)) print(square_diff(3, 4)) 在拥有了基本的数学功能之后,我们可能想为函数增加其它的功能,比如打印输入.我们

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

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

  • 详解python中的装饰器

    在了解装饰器之前,我们需要知道什么闭包是什么鬼! 闭包:在一个函数内定义了一个函数f,并且这个函数f引用外部变量,在把这个函数f当做返回值返回. 上述说了闭包的三个条件: 1 函数内定义了一个函数f 2 f函数引用了外部变量 3 f被当做返回值返回 def t1():#定义t1函数 x=2 def f():#t1函数内部定义了f函数 print(x)#f函数引用了不属于自己内部的变量x return f #f被当做返回值返回 而装饰器有是什么鬼呢?其实闭包的一种运用. 装饰器:在不改变函数(当然

  • Python中的装饰器用法详解

    本文实例讲述了Python中的装饰器用法.分享给大家供大家参考.具体分析如下: 这里还是先由stackoverflow上面的一个问题引起吧,如果使用如下的代码: 复制代码 代码如下: @makebold @makeitalic def say():    return "Hello" 打印出如下的输出: <b><i>Hello<i></b> 你会怎么做?最后给出的答案是: 复制代码 代码如下: def makebold(fn):    

  • 详解Python中的装饰器、闭包和functools的教程

    装饰器(Decorators) 装饰器是这样一种设计模式:如果一个类希望添加其他类的一些功能,而不希望通过继承或是直接修改源代码实现,那么可以使用装饰器模式.简单来说Python中的装饰器就是指某些函数或其他可调用对象,以函数或类作为可选输入参数,然后返回函数或类的形式.通过这个在Python2.6版本中被新加入的特性可以用来实现装饰器设计模式. 顺便提一句,在继续阅读之前,如果你对Python中的闭包(Closure)概念不清楚,请查看本文结尾后的附录,如果没有闭包的相关概念,很难恰当的理解P

  • 快速了解Python中的装饰器

    需要理解的一些概念 要理解Python中的装饰器,我觉得还是应该从最基本的概念开始: 装饰器模式:所谓的装饰器模式,可以简单地理解为"在不改变原有内部实现的情况下,为函数或者类添加某种特性".这样我们就可以将一些与业务无关.具有通用性的代码抽象出来,作为装饰器附加到需要这些代码的函数或者类之上.用面向切面编程的思想解释就是"装饰器应该是一个切面". 函数是一等公民:意思就是函数可以被当成普通变量一样使用.在Python中,可以把函数赋值给变量,可以将函数作为其它函数

  • Python 中@lazyprop 装饰器的用法

    安装 pip install lazyprop 例子1 from lazyprop import lazyprop class Foo(object): def __init__(self): self.load_count = 0 @lazyprop def lazy(self): self.load_count += 1 f = Foo() f.lazy f.lazy f.lazy print(f.load_count) 输出: 1 例子2 from lazyprop import lazy

  • python中的装饰器该如何使用

    目录 1. 需求是怎么来的 装饰器的定义很是抽象,我们来看一个小例子. def foo(): print('in foo()') foo() 这是一个很无聊的函数没错.但是突然有一个更无聊的人,我们称呼他为B君,说我想看看执行这个函数用了多长时间,好吧,那么我们可以这样做: import time def foo(): start = time.time() print('in foo()') time.sleep(2) end = time.time() print(f'used:{end -

  • 一篇文章带你了解Python中的装饰器

    一篇文章带你了解Python中的装饰器

    目录 前言 Python 中的装饰器是什么 语法糖 使用 Python 装饰器修改函数行为 使用 Python 装饰器对函数进行计时 使用 Python 装饰器将有用信息记录到终端 Web app 中使用的装饰器 将参数传递给 Python 装饰器 使用多个 Python 装饰器 总结 前言 本文将带你学习装饰器在 Python 中的工作原理,如果在函数和类中使用装饰器,如何利用装饰器避免代码重复(DRY 原则,Don’t Repeat Yourself ). Python 中的装饰器是什么 装

  • 简单理解Python中的装饰器

    Python的装饰器可以实现在代码运行期间修改函数的上下文, 即可以定义函数在执行之前进行何种操作和函数执行后进行何种操作, 而函数本身并没有任何的改变. 首先, 我们先定义一个函数, 这个函数可以输出我的个人昵称: def my_name(): print "Yi_Zhi_Yu" my_name() # Yi_Zhi_Yu 那假如我需要在个人昵称输出前, 在输出我的个人uid呢, 当然, 要求是不改动现有的my_name函数, 这个时候就可以使用装饰器了 首先, 装饰器也是个函数,

随机推荐