从递归看栈

以你之姓@ 2022-05-11 01:28 169阅读 0赞

很早之前就看过《码农翻身》中的一篇文章----“递归那点事儿”。  
一直很迷恋计算机底层操作系统的故事，却也深感计算机世界的庞大。在前前后后看了这篇文章不下十遍之后，也在不断地积累之后，现在写这篇文章，作为对栈的进一步理解的总结。

## 一：伊始，暗潮涌动： ##

**问题：**  
计算5的阶乘；（我使用javascript）

运行结果：  
![在这里插入图片描述][70]  
分析：上述代码就是递归，通俗的讲就是自己调用自己；  
在执行函数test时，他也调用了另外一个函数，只不过这个函数的代码和上一个函数的代码一模一样！是不是很简单 -\_-  
**看一下机器层面的执行过程：**  
此时就需要引入**栈帧**的概念了：  
1：栈帧将栈分割成N个记录块，每一个记录块的大小是不一样的；  
2：这个记录块实际上是编译器用来实现函数调用的数据结构，通俗来讲就是用于活动记录，他用于记录每次函数调用所涉及的相关信息的记录单元；  
3：栈帧也是一个函数的执行环境，它包括函数的参数，函数的局部变量函数，执行完之后要返回到哪里等等；

说到这里貌似，大约，好像明白了栈帧原来是用于调用函数的，你每调用一次函数他就会形成一个栈帧用于这个被调用函数的运行环境；  
说到这，貌似懂了：上边的test函数在运行时就是形成了一个又一个栈帧啊！  
![在这里插入图片描述][70 1]  
针对上边的递归函数，我画了一幅函数在栈中的执行示意图；  
**栈是一种先进后出的数据结构！！！**  
分析：  
要求计算5的阶乘；  
1）：调用test函数时传入5，即首先在栈中划出一个记录块做为函数`test（5）`的执行环境；执行到最后结果为： `5 * test（4）`；  
2）：上一个函数的返回值中调用函数test（4），因此继续指向新的记录块，用于执行函数`test（4）`；执行到最后结果为： `4 * test（3）`；  
3）：上一个函数的返回值中调用函数test（3），因此继续指向新的记录块，用于执行函数`test（3）`；执行到最后结果为： `3 * test（2）`；  
4）：上一个函数的返回值中调用函数test（2），因此继续指向新的记录块，用于执行函数`test（2）`；执行到最后结果为： `2 * test（1）`；  
5）：上一个函数的返回值中调用函数test（1），因此继续指向新的记录块，用于执行函数`test（1）`；执行到最后`test（1）=1`；  
**此时进栈操作已经到达了递归终止的条件，为了计算出最后的test（5）的值需要执行出栈操作；**  
![在这里插入图片描述][70 2]  
如上图，我画了一幅出栈示意图；栈是先进后出的，所以最后进的要先出。  
1）：test（1）出栈，返回值为1；  
2）：栈帧test（2）接收test（1）返回值进行计算得出`test（2） = 2 * 1 = 2`；  
3）：test（2）出栈，栈帧test（3）接收test（2）返回值进行计算得出`test（3） = 3 * 2 = 6`；  
4）：test（3）出栈，栈帧test（4）接收test（3）返回值进行计算得出`test（4） = 4 * 6 = 24`；  
5）：test（4）出栈，栈帧test（5）接收test（4）返回值进行计算得出`test（5） = 5 * 24 = 120`；  
6）：test（5）出栈，返回值120，此时表示这一段程序已经执行完毕，计算得出5的阶乘是120；  
**递归函数写到这一步，貌似是已经完美了，但是你有没有想过：每一个函数`test（n） = n * test (n-1)`因此每一个栈帧不仅需要保存n值还要记录下一个栈帧的返回值，然后才能计算出来当前栈帧的结果，因此使用多个栈帧是不可避免的，计算5的阶乘就使用了5个栈帧，那要是计算100的呢？10000的呢？。。。。这TM是不是有点始料未及了？栈的大小也是有限的，你就这么用下去，他不给你溢出才怪。因此我给这一节命名为：“伊始，暗潮涌动”**；

## 二：锤炼，万法归一 ##

上边的程序就已经暴露出来了缺陷，也就是栈的大小是有限的，所以上述递归函数是可以优化的；  
**优化后的函数为：**

执行结果为：  
![在这里插入图片描述][70 3]

**分析：鉴于前边递归函数的缺陷，修改了递归算法如上述代码，不知道你有没有发现每一次递归时return的内容不再是一个表达式，而是这个函数本身！这个好处是巨大的！因为他使用一个栈帧就可以搞定！这个函数有着良好的栈帧复用性！这种方式也就是传说中的尾递归了！**

**为什么前边的栈帧就不可以复用呢？咱们假设他也是可以复用的，他要是复用了岂不是把先前保存的n值丢掉了？那后边的test（n-1）计算出来之后还有什么用？因此他是绝对做不到复用的！**

**在尾递归中返回值不是表达式的一部分，也就是说他栈帧的复用不会有任何的隐患，不会管头不顾腚-\_- 所以当返回值不是表达式的一部分时也就可以称为尾递归了；**

## 最后的话： ##

1 ： 这是优化吗？在明白了道理之后，怕就不能再称之为优化了吧，而是必须应当要做的！  
A：你会优化递归吗？  
B：什么优化？栈帧复用难道不是要直接考虑进来的吗？  
2：最后，离不开的只是习惯而已；

[70]: /images/20220511/e06d6939c713420daa8c601b2725f385.png
[70 1]: /images/20220511/2e59b1809bcb4c718f0956d27f648ba6.png
[70 2]: /images/20220511/6c02cf311e5a4167bc23e8f5c9826e60.png
[70 3]: /images/20220511/9b3d6135374242c69f6709027b16620c.png