这期内容当中小编将会给大家带来有关使用Python实现尾递归优化,文章内容丰富且以专业的角度为大家分析和叙述,阅读完这篇文章希望大家可以有所收获。
在传统的递归中,典型的模式是,你执行第一个递归调用,然后接着调用下一个递归来计算结果。这种方式中途你是得不到计算结果,知道所有的递归调用都返回。这样虽然很大程度上简洁了代码编写,但是让人很难它跟高效联系起来。因为随着递归的深入,之前的一些变量需要分配堆栈来保存。
尾递归相对传统递归,其是一种特例。在尾递归中,先执行某部分的计算,然后开始调用递归,所以你可以得到当前的计算结果,而这个结果也将作为参数传入下一次递归。这也就是说函数调用出现在调用者函数的尾部,因为是尾部,所以其有一个优越于传统递归之处在于无需去保存任何局部变量,从内存消耗上,实现节约特性。
下面以递归计算加法的实例来说明:
我们用Python实现:
普通递归调用:
def递归(n): 如果n==1: 返回n 其他: 返回n +递归(n - 1)
调用这个函数递归(5),编译器会执行:
递归(5)
5 +递归(4)
5 +(4 +递归(3))
5 +(4 +(3 +递归(2)))
5 +(4 + 3 +(2 +递归(1))))
5 + (4 + (3 + (2 + 1)))
15
此处编译器会分配递归栈来保存中间结果
下来看尾递归实现:
def tail_recursion (n、总=0): 如果n==0: 返回总 其他: 返回tail_recursion (n - 1,总+ n)此时,编译器做的工作:
tail_recursion (5,0)
tail_recursion (4、5)
tail_recursion (3、9)
tail_recursion (2, 12)
tail_recursion (1、14)
tail_recursion 15 (0, 15)
你可以看到当前时刻的计算值作为第二个参数传入下一个递归,使得系统不再需要保留之前计算结果。
尾递归的优势就显而易见了。
但是python本身不支持尾递归(没有对尾递归做优化),而且对递归的次数有限制,当递归深度超过1000时,会抛出异常:
分别执行递归(998),tail_recursion (998 0)
输出:
498501
498501
没有问题,当调用
递归(999),tail_recursion(999 0)时,
输出:RuntimeError:最大递归深度超过
因为递归次数超出了1000
有人对此为python的尾递归写了一个优化版本,让python突破递归调用1000次的限制:尾部调用优化修饰符(python食谱)
上述就是小编为大家分享的使用python实现尾递归优化了,如果刚好有类似的疑惑,不妨参照上述分析进行理解。如果想知道更多相关知识,欢迎关注行业资讯频道。
使用Python实现尾递归优化
