首先,递归调用是函数调用自己本身,在计算机中,函数调用是通过栈(stack)这种数据结构实现的,每当进入一个函数调用,栈就会加一层栈帧,每当函数返回,栈就会减一层栈帧。由于栈的大小不是无限的,所以,递归调用的次数过多,会导致栈溢出。
尾递归是指,在函数返回的时候,调用自身本身,并且,return语句不能包含表达式。这样,编译器或者解释器就可以把尾递归做优化,使递归本身无论调用多少次,都只占用一个栈帧,不会出现栈溢出的情况。
但是,Python解释器没有做优化,即使把递归函数修改成尾递归的方式依然无法解决问题。
所以参考了这位老哥的代码
链接: Python尾递归优化.
import sysclass TailRecurseException(BaseException):def __init__(self, args, kwargs):self.args = argsself.kwargs = kwargsdef tail_call_optimized(g):"""This function decorates a function with tail calloptimization. It does this by throwing an exceptionif it is it's own grandparent, and catching suchexceptions to fake the tail call optimization.This function fails if the decoratedfunction recurses in a non-tail context."""def func(*args, **kwargs):f = sys._getframe()if f.f_back:if f.f_back.f_back:if f.f_back.f_back.f_code == f.f_code:passif 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.argskwargs = e.kwargsfunc.__doc__ = g.__doc__return func@tail_call_optimizeddef demo_2(n, res=1):if n <= 1:return resreturn demo_2(n-1, n*res)print(demo_2(9999))
拓展:
栈帧(frame)
栈帧表示程序运行时函数调用栈中的某一帧。想要获得某个函数相关的栈帧,则必须在调用这个函数且这个函数尚未返回时获取。可以使用sys模块的_getframe()函数、或inspect模块的currentframe()函数获取当前栈帧。这里列出来的属性全部是只读的。
f_back: 调用栈的前一帧。
f_code: 栈帧对应的code对象。
f_locals: 用在当前栈帧时与内建函数locals()相同,但你可以先获取其他帧然后使用这个属性获取那个帧的locals()。
f_globals: 用在当前栈帧时与内建函数globals()相同,但你可以先获取其他帧……
第二次调用时:
f.f_back.f_back.f_code和f.f_code为同一对对象调用