时间:2021-05-22
在传统的递归中,典型的模式是,你执行第一个递归调用,然后接着调用下一个递归来计算结果。这种方式中途你是得不到计算结果,知道所有的递归调用都返回。 这样虽然很大程度上简洁了代码编写,但是让人很难它跟高效联系起来。因为随着递归的深入,之前的一些变量需要分配堆栈来保存。
尾递归相对传统递归,其是一种特例。在尾递归中,先执行某部分的计算,然后开始调用递归,所以你可以得到当前的计算结果,而这个结果也将作为参数传入下一次递归。这也就是说函数调用出现在调用者函数的尾部,因为是尾部,所以其有一个优越于传统递归之处在于无需去保存任何局部变量,从内存消耗上,实现节约特性。
下面以递归计算加法的实例来说明:
我们用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
此处编译器会分配递归栈来保存中间结果
下来看尾递归实现:
此时,编译器做的工作:
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)
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
java仿Servlet生成验证码实例详解实现原理:使用BufferedImage对象的Graphics来进行绘制,然后输出成一张图片进行保存实现代码及详解:p
本文实例讲述了JS尾递归的实现方法及代码优化技巧。分享给大家供大家参考,具体如下:在学习数据结构和算法的时候,我们都知道所有的递归都是可以优化成栈+循环的。对于
Android实现获取手机里面的所有图片详解及实例实现代码:publicclassMainActivityextendsActivity{//查看图片按钮pri
java读取resources文件详解及实现代码Java项目中,经常需要将资源文件打包放在项目中,然后在项目中去读取对应的文件。实现代码:Stringstr=R
本文实例讲述了python中尾递归用法。分享给大家供大家参考。具体分析如下:如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的。当