尾递归是指在函数返回时调用自身,并且 return
语句不能包含表达式。通过这种方式,编译器或解释器可以对尾递归进行优化,从而使递归本身仅占用一个栈帧,而不会发生栈溢出。
Python 的尾递归优化对于编译到机器码执行的代码(不管是 AOT 还是 JIT),简单来讲,只要将 call
…ret
指令改为 jump
…,就可以复用同一个栈帧,当然还有很多额外工作需要做。对于解释执行的代码,解释器本身有很多机会可以动态修改栈帧来做尾递归优化。
但是 CPython 的实现并没有支持尾递归优化,并且默认限制了递归调用层数为1000(通过 sys.getrecursionlimit
函数可以查看)。不过,这并不代表我们没有办法在 Python 中实现尾递归优化,可以参考廖雪峰的 Python 教程或者使用 TailCallOptimizationDecorator
优化版本来实现。