进一步讨论递归函数——递归与栈

逃离我推掉我的手 2022-08-04 13:40 299阅读 0赞

递归函数，在函数的执行函数中，需多次进行自我调用。那么，递归函数是如何执行的？先看任意两个函数之间进行调用的情形。用函数和被调用函数\[若在函数A中调用了函数B，则称函数A为调用函数，称函数B为被调用函数。\]之间的链接及信息交换需通过栈来进行。在上一篇递归函数的讲解中主要对递归的定义和一些应用进行了介绍，最近学习了一点数据结构的知识，看到了递归函数的工作原理其实使用栈来实现的我才恍然大悟。知识学多了，真的可以连接到一起的。

通常，当在一个函数的运行期间调用另一个函数时，在运行被调用函数之前，系统需先完成3件事：（1）将所有的实在参数、返回地址等信息传递给被调用函数保存；（2）为被调用函数的局部变量分配存储区；（3）将控制转移到被调函数的入口。而从被调用函数返回调用函数之前，系统也应完成3件工作：（1）保存被调函数的计算结果；（2）释放被调函数的数据区；（3）依照被调函数保存的返回地址将控制转移到调用函数。当有多个函数构成嵌套调用时，按照“后调用先返回”的原则，上述函数之间的信息传递和控制转移必须通过“栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为它在栈顶分配一个存储区，每当从一个函数退出时，就释放它的存储区，则当前正运行的函数的数据区必在栈顶。

就像是下面这个Fibonacci函数的运算原理，就是利用了函数调用函数，在栈顶分配存储区，因为栈是一种运算受限制的线性表，采用的是先进先出的方法，在栈顶一端进行操作，先调用的，先分配，当退出的时候，先释放的时候最顶上的一次调用空间，也就是最后一次调用。这就很好的解释了递归的一层一层的调用关系。

![SouthEast][]

递归优点：

结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性

递归缺点：

递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多关于递归与非递归的效率，空间复杂度的话，非递归完胜。时间复杂度要具体问题具体分析，一般来说递归的执行步数较多，非递归的执行频率较多。 在用栈的情况下，非递归确实不如递归的效率。

什么时候递归用到栈？

除内联函数外，调用函数的时候对应的汇编代码必然有。call 函数地址（传参方式根据调用方式和对应语言有所不同哈）。其中call命令的含义就是把返回地址打入栈中然后跳到函数地址执行，因此必然会使用栈。

总结：

J2SE和数据结构一起复习，碰撞出新的火花，快来发现吧。

[SouthEast]: /images/20220731/44bacccb58274dc9aa8f7eb1b5659194.png