尾递归是指,在函数返回时,调用自身本身,即return语句不能包含表达式
。
尾递归与一般的递归不同在于对内存
的占用:普通递归创建stack累积而后计算收缩,尾递归只会占用恒量的内存。
def recsum(x):
if x == 1:
return x
else:
return x+recsum(x-1) # 这里的return语句返回的是表达式
调用recsum(5),Python调试器发生如下状况:
recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 +1)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
15
曲线代表内存占用的峰值,先达到顶峰再收缩。
我们通常不希望这样的事情发生,所以使用迭代,只占用常量stack space(更新这个栈,而非扩展它)。
def tailrecsum(x,running_total=0):
if x == 0:
return running_total
else:
return tailrecsum(x - 1,running_total + x) # 尾递归的返回是调用自身
调用tailrecsum(5),Python调试器中发生如下状况:
tailrecum(5,0)
tailrecum(4,5)
tailrecum(3,9)
tailrecum(2,12)
tailrecum(1,14)
tailrecum(0,15)
15
观察到,tailrecsum(x,y)中的形式变量y
的实际变量值是不断更新的;而普通递归的每个recsum()调用中y值不变,仅在层级上加深。所以,尾递归是把变化的参数传递给递归函数的变量了。
tips:一定要注意这个!!在做毕业论文的过程中因为忽略参数的变化,导致一直出错!
当编译器检测到一个函数调用时尾递归时,它就覆盖当前的活动记录,而不是在栈中去创建一个新的,这样所使用的栈空间就大大缩减,使得实际的运行效率变得更高,这个过程也叫编译器把尾递归做优化。
python编译器没有尾递归优化的功能,递归深度超过1000时会报错,因此需要我们通过实现一个tail__call__optimized装饰器来优化尾递归:
# Python3的装饰器
import sys
class TailRecurseException(BaseException):
def __init__(self,args,kwargs):
self.args = args
self.kwargs = kwargs
def tail_call_optimized(g):
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 as e:
args = e.args
kwargs = e.kwargs
func.__doc__ = g.__doc__
return func
只要在尾递归函数的前面加上@tail__call__optimized
就可以完成装饰器的调用:
@tail_call_optimized
def fact_iter(num,product):
print(product)
if num == 1:
return product
return fact_iter(num-1,product+1)
tail__call__optimized
实现尾递归优化的原理:当递归函数被该装饰器修饰后,递归调用在装饰器while循环
内部进行,每当产生新的递归调用栈时,就捕获当前尾调用函数的参数,并抛出异常,从而销毁递归栈并使用捕获的参数手动调用递归函数。
参考资料:
(24条消息) Python尾递归_BrownWong的博客-CSDN博客_python 尾递归
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。