尾递归优化原理与Python实现（以Fibonacci数列和小明爬楼梯问题为例）

众所周知，在函数递归调用时，要保存函数调用的位置以便使得被调函数结束后能够返回正确的位置，这个信息保存在线程栈中。由于栈的空间有限，所以如果函数递归调用深度超过一定限制，会导致栈崩溃。并且，如果需要保存大量返回位置并且逐级返回的话，也会耗费大量的时间，使得代码运行速度非常慢。

所谓尾递归，是指函数调用出现在函数的尾部最后一条语句，并且函数返回值不作为其他表达式的一部分。如果编译器支持尾递归优化的话，这种情况下将不会保存返回位置，从而避免栈崩溃。因此，通过改写递归函数，改用尾递归的话，会大幅度提高运行速度，并且不会栈崩溃。

例如，下面是经典的Fibonacci数列中第n项求解的问题，第一段代码没有使用尾递归，第二段代码使用了尾递归。

上面两段代码的运行速度有天壤之别，如下图所示：

bingo，太棒了，果然速度提高很多。

然而，不要高兴的太早，把代码中的n修改为1200，交换两个函数调用的顺序，重新测试结果如下：

还是栈崩溃。。。。

看来要真正实现尾递归优化，只是改写代码还不够啊，还需要编译器或解释器的支持才行。从上面的情况来看，Python解释器默认并没有支持尾递归优化。

网上有一个使用修饰器修改栈中参数实现尾递归优化的方法，不过代码是Python 2的，我进行了简单修改，变成了Python 3的版本。

为了验证代码的正确性，上面的代码同时给出了迭代法实现，并且把问题规模增大到2300，运行结果如下，可见迭代还是无敌的啊：

再例如，小明爬楼梯的问题，问题描述可以参考以前的推文Python两种方法求解登楼梯问题（京东2016笔试题），如果改为尾递归的话，继续使用上面代码中的尾递归修饰器，代码如下：

运行结果如下：

上面的实现看起来已经很完美了，但又是类定义，又是修饰器，还要操作栈帧，好像很复杂的样子，有没有更简单的实现呢？

答案是确定的，以小明爬楼梯的问题为例：使用嵌套函数定义+生成器函数实现尾递归优化的代码如下：

这样真的可以吗？我们让事实来说话，修改测试代码：

运行结果如下：