Python尾递归优化实现代码及原理详解
作者:lincappu 发布时间:2023-11-08 15:35:28
在传统的递归中,典型的模式是,你执行第一个递归调用,然后接着调用下一个递归来计算结果。这种方式中途你是得不到计算结果,知道所有的递归调用都返回。 这样虽然很大程度上简洁了代码编写,但是让人很难它跟高效联系起来。因为随着递归的深入,之前的一些变量需要分配堆栈来保存。
尾递归相对传统递归,其是一种特例。在尾递归中,先执行某部分的计算,然后开始调用递归,所以你可以得到当前的计算结果,而这个结果也将作为参数传入下一次递归。这也就是说函数调用出现在调用者函数的尾部,因为是尾部,所以其有一个优越于传统递归之处在于无需去保存任何局部变量,从内存消耗上,实现节约特性。
下面以递归计算加法的实例来说明:
我们用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)
来源:https://www.cnblogs.com/lincappu/p/12510820.html
猜你喜欢
- 有一个同学在Gne的群里面咨询如何通过Selenium获取当前鼠标指向的元素,在我讲了方法以后,他过了两天又来问:那么,我今天就来写一篇文章
- 1、Python数据存储(压缩)(1)numpy.save , numpy.savez , scipy.io.savematnumpy和sc
- 使用Django中遇到这样一个需求,对一个表的几个字段做 联合唯一索引,例如学生表中 姓名和班级 2个字段在一起表示一个唯一记录。Djang
- 常有人因为页面的面积问题,想在一个窄小的地方,显示一条条的信息,顺序往上滚动,在经典的BBS里,有一个随机上滚动的JS,好些人用不了,现在蛋
- 实现功能QuestType 1->查询语句, 2->更新语句, 3->删除语句, 4->插入语句<
- 方法一:读取文件时设置代码如下:Data = pd.read_excel(level_path, sheet_name=0, encodin
- asp分页做为一个经典的asp问题,有着非常丰富的分页形式和分页方法,但是大多数的asp分页都是使用VBscript作为服务器端的脚本,本文
- 什么是 Python 中的 Lambda 函数今天我们来学习 Python 中的 lambda 函数,并探讨使用它的优点和局限性Let
- 1、你需要通过指定的文本模式去检查字符串的开头或者结尾,比如文件名后缀,URL Scheme 等等。检 查 字 符 串 开 头 或 结 尾
- Window.Open详解 一、window.open()支持环境:JavaScript1.0+/JScript1.0+/Nav2
- 通常来说,一个Python程序可以从键盘读取输入,也可以从文件读取输入;而程序的结果可以输出到屏幕上,也可以保存到文件中便于以后使用。本文就
- 本文实例分析了php字符串截取函数用法。分享给大家供大家参考。具体分析如下:php自带的截取字符串的函数只能处理英文,数字的不能截取中文混排
- 本文实例讲述了Python简单获取自身外网IP的方法。分享给大家供大家参考,具体如下:#encoding=utf-8#author: wal
- 用Python基于Google Bard做一个交互式的聊天机器人之前已经通过浏览器试过了 Google Bard ,更多细节请看: Try
- 本文利用python opencv进行图像的边缘检测,一般要经过如下几个步骤:1、去噪如cv2.GaussianBlur()等函数;2、计算
- 三个工具包python操作excel的三个工具包如下,注意,只能操作.xls,不能操作.xlsx。• xlrd: 对excel进行读相关操作
- 和其他语言不一样,传递参数的时候,python不允许程序员选择采用传值还是传引用。Python参数传递采用的肯定是“传对象引用”的方式。实际
- 描述:使用QtDesignner设计界面,pyQt5+python3实现主体方法制作的猜数字游戏。游戏规则:先选择游戏等级:初级、中级、高级
- 如下所示:import urllib,json,requestsurl = 'http://127.0.0.1:8000/accou
- 出现这样的问题是当你浏览UTF-8编码的时候,服务器默认用UTF-8的引擎来输出html,当你用再浏览GB2312的页面时,它还是用UTF-