Python尾递归优化实现代码及原理详解

站长资源 2024/11/24 佚名

2 0 1

在传统的递归中，典型的模式是，你执行第一个递归调用，然后接着调用下一个递归来计算结果。这种方式中途你是得不到计算结果，知道所有的递归调用都返回。这样虽然很大程度上简洁了代码编写，但是让人很难它跟高效联系起来。因为随着递归的深入，之前的一些变量需要分配堆栈来保存。

尾递归相对传统递归，其是一种特例。在尾递归中，先执行某部分的计算，然后开始调用递归，所以你可以得到当前的计算结果，而这个结果也将作为参数传入下一次递归。这也就是说函数调用出现在调用者函数的尾部，因为是尾部，所以其有一个优越于传统递归之处在于无需去保存任何局部变量，从内存消耗上，实现节约特性。
下面以递归计算加法的实例来说明：

我们用python实现：

普通递归调用：

def recursion(n):
  if n==1:
    return n
  else:
    return n+recursion(n-1)

调用这个函数recursion（5），编译器会执行：

recursion(5)
5+recursion(4)
5+(4+recursion(3))
5+(4+(3+recursion(2)))
5+(4+(3+(2+recursion(1))))
5+(4+(3+(2+1)))
15

此处编译器会分配递归栈来保存中间结果

下来看尾递归实现：

def tail_recursion(n,total=0):
  if n==0:
    return total
  else:
    return tail_recursion(n-1, total+n)

此时，编译器做的工作：

tail_recursion(5,0)
tail_recursion(4,5)
tail_recursion(3,9)
tail_recursion(2,12)
tail_recursion(1,14)
tail_recursion(0,15)
15

你可以看到当前时刻的计算值作为第二个参数传入下一个递归，使得系统不再需要保留之前计算结果。

尾递归的优势就显而易见了。

但是python本身不支持尾递归（没有对尾递归做优化），而且对递归的次数有限制，当递归深度超过1000时，会抛出异常：

分别执行recursion(998),tail_recursion(998,0)

输出：

498501
498501

没有问题，当调用

recursion(999),tail_recursion(999,0)时，

输出：RuntimeError: maximum recursion depth exceeded

因为递归次数超出了1000

有人对此为Python的尾递归写了一个优化版本，让Python突破递归调用1000次的限制：Tail Call Optimization Decorator (Python recipe)

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。

Python,尾递归,优化

广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！

评论“Python尾递归优化实现代码及原理详解”

暂无评论...

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

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

艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕，并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时，他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中，玩家将会进入一个全新的海盗主题大逃杀式限时活动，其中包含极高的风险和史诗级的奖励。
《强袭风暴》不是普通的战场，作为一个独立于主游戏之外的活动，玩家可以用大逃杀的风格来体验《魔兽世界》，不分职业、不分装备（除了你在赛局中捡到的），光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式，玩家在加入海盗主题的预赛大厅区域前，可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹，《巨龙崛起》和《魔兽世界：巫妖王之怒经典版》的玩家都可以获得奖励。

更新日志

2024年11月24日

Python尾递归优化实现代码及原理详解

Python判断变量是否是None写法代码实例

Python hashlib模块的使用示例

评论“Python尾递归优化实现代码及原理详解”

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

更新日志

友情链接