脚本专栏

Python中使用装饰器来优化尾递归的示例
脚本专栏 2025/4/27 佚名
3 2

尾递归简介
尾递归是函数返回最后一个操作是递归调用，则该函数是尾递归。
递归是线性的比如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相比大概造成了五倍的时间开销。

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

标签：
Python,尾递归,装饰器,递归
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！ 如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
白云城资源网 Copyright www.dyhadc.com

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

暂无“Python中使用装饰器来优化尾递归的示例”评论...
www.dyhadc.com 白云城资源网
129,905影音资源
244,626技术资源
111,817软件资源
578,645站长资源

《魔兽世界》大逃杀！60人新游玩模式《强袭风暴》3月21日上线

暴雪近日发布了《魔兽世界》10.2.6 更新内容，新游玩模式《强袭风暴》即将于3月21 日在亚服上线，届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。

艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕，并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时，他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中，玩家将会进入一个全新的海盗主题大逃杀式限时活动，其中包含极高的风险和史诗级的奖励。

《强袭风暴》不是普通的战场，作为一个独立于主游戏之外的活动，玩家可以用大逃杀的风格来体验《魔兽世界》，不分职业、不分装备（除了你在赛局中捡到的），光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式，玩家在加入海盗主题的预赛大厅区域前，可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹，《巨龙崛起》和《魔兽世界：巫妖王之怒 经典版》的玩家都可以获得奖励。

更新日志

友情链接

杰晶网络 DDR爱好者之家 南强小屋 黑松山资源网 白云城资源网 更多链接
白云城资源网 Copyright www.dyhadc.com