Question

递归可以用栈实现吗

Answer 1

递归可以用栈实现吗？栈是如何实现递归的

在高级语言中，调用自己和其他函数并没有本质的不同。我们把一个直接调用自己或通过一系列的调用语句间仿明伏接地调用自己的函数，称做递归函数。

当然，写递归程序最怕的就是陷入永不结束的无穷递归中，所以，毎个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出。比如刚才的例子，总有一次递归会使得i < 2的，这样就可以执行return i的语句而不用继续递归了。
对比了两种实现斐波那契的代码。迭代和递归的区别是：迭代使用的是循环结构，递归使用的是选择结构。

递槐碧归能使程序的结构更清晰、更简洁、更容易让人理解，从而减少读懂代码的时间。但是大量的递归调用会建立函数的副本，会耗费大量的时间和内存。
迭代则不需要反复调用函数和占用额外的内存。因此我们应该视不同 情况选择不同的代码实现方式。
那么我们讲了这么多递归的内容，和栈有什么关系呢？这得从计算机系统的内部说起。

前面我们已经看到递归是如何执行它的前行和退回阶段的。递归过程退回的顺序是它前行顺序的逆序。在退回过程中，可能要执行某些动作，包括恢复在前行过程中存储起来的某些数据。
这种存储某些数据备携，并在后面又以存储的逆序恢复这些数据，以提供之后使用的需求，显然很符合栈这样的数据结构，因此，编译器使用栈实现递归就没什么好惊讶的了。

简单的说，就是在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段，位于栈顶的局部变量、参数值和返回地址被弹出，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态。

递归调用其实就是栈，栈有先进后出的特点，递归调用的实质也就是循环调用，我写一个简单的例子吧：