递归调用的理解引申函数调用过程中栈指针的变化

以前将递归理解成调用自己，怎么都理解不了。

后来理解了，其实就把递归调用理解成普通调用好了，只不过调用的是和自己原来一样的函数，但是记得他是从头重新调用了一遍

在栈空间里有独立的位置。

一直到最后一层调用的时候才开始返回。

所以严格意义上，他不是调用自己，而是调用一个复制了一份的另外一个函数。但他是两个函数，只不过共用了一个函数体。

所以最外面一层该进行的所有运算还是得进行，省不了。

那么它和普通函数调用的区别就在这里，既要满足能够跳转，跳转出去的每个函数能够用，又要满足自己能够执行下去。

引申了解一下普通程序调用过程中的栈指针的变化过程：

https://www.cnblogs.com/zlcxbb/p/5759776.html

我们先来了解一个概念，栈帧(stack frame)，机器用栈来传递过程参数，存储返回信息，保存寄存器用于以后恢复，以及本地存储。为单个过程(函数调用)分配的那部分栈称为栈帧。栈帧其实 是两个指针寄存器，寄存器%ebp为帧指针（指向该栈帧的最底部），而寄存器%esp为栈指针（指向该栈帧的最顶部），当程序运行时，栈指针可以移动(大多数的信息的访问都是通过帧指针的，换句话说，就是如果该栈存在，%ebp帧指针是不移动的，访问栈里面的元素可以用-4(%ebp）或者8(%ebp)访问%ebp指针下面或者上面的元素)。总之简单 一句话，栈帧的主要作用是用来控制和保存一个过程的所有信息的。栈帧结构如下所示：

此处注意：这里面有一个错误，即：“保存的寄存器、局部变量和临时值”处应该是ebp-4。

栈是从高地址向低地址存储。所以越是低的地址，越是靠后入栈。

如果你已经对这个图已经非常了解了，那么就没有必要再看下去了。因为下面的内容都是对这幅图的讲解。

　　假设过程P（调用者）调用过程Q（被调用者），则Q的参数放在P的栈帧中。另外，当P调用Q时，P中的返回地址被压入栈中，形成P的栈帧的末尾 （返回地址就是当程序从Q返回时应该继续执行的地方）。Q的栈帧从保存的帧指针的值开始，后面到新的栈指针之间就是该过程的部分了。

理论解说：

https://www.cnblogs.com/zhq--blog/p/7354056.html

一、栈
     在说函数递归的时候，顺便说一下栈的概念。
     栈是一个后进先出的压入(push)和弹出(pop)式数据结构。在程序运行时，系统每次向栈中压入一个对象，然后栈指针向下移动一个位置。当系统从栈中弹出一个对象时，最近进栈的对象将被弹出。然后栈指针向上移动一个位置。程序员经常利用栈这种数据结构来处理那些最适合用后进先出逻辑来描述的编程问题。这里讨论的程序中的栈在每个程序中都是存在的，它不需要程序员编写代码去维护，而是由运行是系统自动处理。所谓的系统自动维护，实际上就是编译器所产生的程序代码。尽管在源代码中看不到它们，但程序员应该对此有所了解。
     再来看看程序中的栈是如何工作的。当一个函数(调用者)调用另一个函数(被调用者)时，运行时系统将把调用者的所有实参和返回地址压入到栈中，栈指针将移到合适的位置来容纳这些数据。最后进栈的是调用者的返回地址。当被调用者开始执行时，系统把被调用者的自变量压入到栈中，并把栈指针再向下移，以保证有足够的空间存储被调用者声明的所有自变量。当调用者把实参压入栈后，被调用者就在栈中以自变量的形式建立了形参。被调用者内部的其他自变量也是存放在栈中的。由于这些进栈操作，栈指针已经移动所有这些局部变量之下。但是被调用者记录了它刚开始执行时的初始栈指针，以他为参考，用正或负的偏移值来访问栈中的变量。当被调用者准备返回时，系统弹出栈中所有的自变量，这时栈指针移动了被调用者刚开始执行时的位置。接着被调用者返回，系统从栈中弹出返回地址，调用者就可以继续执行了。当调用者继续执行时，系统还将从栈中弹出调用者的实参，于是栈指针回到了调用发生前的位置。
     可能刚开始学的人看不太懂上面的讲解，栈涉及到指针问题，具体可以看看一些数据结构的书。要想学好编程语言，数据结构是一定要学的。

二、递归
     递归，是函数实现的一个很重要的环节，很多程序中都或多或少的使用了递归函数。递归的意思就是函数自己调用自己本身，或者在自己函数调用的下级函数中调用自己。
     递归之所以能实现，是因为函数的每个执行过程都在栈中有自己的形参和局部变量的拷贝，这些拷贝和函数的其他执行过程毫不相干。这种机制是当代大多数程序设计语言实现子程序结构的基础，是使得递归成为可能。假定某个调用函数调用了一个被调用函数，再假定被调用函数又反过来调用了调用函数。这第二个调用就被称为调用函数的递归，因为它发生在调用函数的当前执行过程运行完毕之前。而且，因为这个原先的调用函数、现在的被调用函数在栈中较低的位置有它独立的一组参数和自变量，原先的参数和变量将不受影响，所以递归能正常工作。程序遍历执行这些函数的过程就被称为递归下降。
     程序员需保证递归函数不会随意改变静态变量和全局变量的值，以避免在递归下降过程中的上层函数出错。程序员还必须确保有一个终止条件来结束递归下降过程，并且返回到顶层。

递归的基本原理：
https://blog.csdn.net/ysuncn/article/details/1793896

１　每一次函数调用都会有一次返回．当程序流执行到某一级递归的结尾处时，它会转移到前一级递归继续执行．

２　递归函数中，位于递归调用前的语句和各级被调函数具有相同的顺序．如打印语句 #1 位于递归调用语句前，它按照递
　　归调用的顺序被执行了 4 次．

３　每一级的函数调用都有自己的私有变量．

４　递归函数中，位于递归调用语句后的语句的执行顺序和各个被调用函数的顺序相反．

５　虽然每一级递归有自己的变量，但是函数代码并不会得到复制．

６　递归函数中必须包含可以终止递归调用的语句．