函数递归调用？看这文就够了 _递归

文章插图
作者 | Cooper Song
责编 | Elle
出品 | 程序人生（ID：coder_life）
我猜，大多数程序员第一次接触函数的递归调用都是在算斐波那契数列某项值的时候，这是函数递归调用最常见的应用之一。规定第一项和第二项为1，后面的项，每一项都是其前面两项的和。
【函数递归调用？看这文就够了】用公式表示就是f(n)=f(n-2)+f(n-1) 。
而进一步转化，就是f(n)=[f(n-2-2)+f(n-2-1)]+[f(n-1-2)+f(n-1-1)] 。
很明显，这是一个递归的过程。
递归的优点是算法简单、容易理解，代码行数少。
但递归也有缺点，咱们将上面的f(n)再化简一下就变成了f(n)=[f(n-4)+f(n-3)]+[f(n-3)+f(n-2)]，可以看出，f(n-3)被计算了两次，而f(n-4)+f(n-3)就是再计算f(n-2)，又与最后一项f(n-2)是一样的，f(n-2)也被重复计算了。因此，递归的一大缺点就是存在大量的重复计算，运行起来浪费时间也浪费空间。
递归的另一个缺点是递归的层数不能太多（不能递归太深）。那递归得太深了会怎样呢？答案是会爆栈。那么什么是爆栈呢？又是怎样引发爆栈的呢？下面就要从最底层的角度讲一讲函数调用及函数递归调用的原理，相信读完了就会找到答案。
这就要先从程序的链接和装入说起了。
程序的链接（Link）
一个程序是由多个模块构成的，以C语言为例，有头文件<stdio.h>，只有引用了这个头文件你才能使用scanf和printf；还有头文件<string.h>，只有引用了这个头文件你才能直接调用strlen函数得到字符串的大小。所谓程序的链接，就是将整个程序的所有目标模块（比如程序员自己写的头文件和函数）以及其他所需要的库函数装配成一个完整的装入模块。
原来每个模块都有每个模块的逻辑地址，经过链接后，形成了统一的从0开始的逻辑地址，如下图所示。

文章插图
如何理解模块？看上图大概就有了概念，一个函数就是一个模块。
程序的装入（Load）
学过计算机组成原理的同学都知道，在计算机中有个部件叫程序计数器（Program Counter，简称PC），它存放的是程序要执行的下一条指令的地址，CPU要到内存当中去取指令，取到CPU中进行译码分析然后执行。
程序原本存储在磁盘上，因此只经过链接还不能运行，还需要装入主存（内存），CPU通过PC提供的线索到内存中去取指令，如此循环往复，程序才得以运行下去。虽然程序的第一条指令的逻辑地址是0，但它装入内存时在内存中的地址可不是0，因为内存中的低地址是留给系统使用的，也就是系统区，比系统区的地址高的空间才是留给用户使用的，也就是用户区。虽然装入内存后其地址不再是从0开始，但其相对地址是不变的，将上面链接好的装入模块装入内存，内存空间示意图如下。

文章插图
函数的调用
所谓函数的调用，就是程序原本在主模块中顺序执行，遇到调用指令暂时到别的模块执行，在别的模块执行完后再返回主模块的下一条指令继续执行，如下图所示。

文章插图
为什么可以执行着执行着就跳到别的模块执行了？又为什么在别的模块执行完了又回到原来的模块执行了呢？之所以能跳到别的模块执行，是因为函数调用指令就指明了目标模块的首地址，将目标模块的首地址传送给了程序计数器PC，就中断了程序的顺序执行，然后进入目标模块执行。之所以执行完子模块还能回到主模块中执行，是因为内存中有一个专门实现函数调用的栈区，在执行调用指令的时候，就将主模块调用指令之后的指令的地址入了栈，当子模块执行到返回指令的时候，再出栈，将栈顶元素（也就是主模块中要执行的下一条指令的地址）传给PC，程序的执行就又回到了主模块。
假设模块A中的指令是：
add ax,bx ;本条指令的地址为10000
call B ;调用模块B本条指令的地址为10001
mov dx,ax ;本条指令的地址为10002
假设模块B中的指令是：
sub cx,dx ;本条指令的地址为15000
mov bx,cx ;本条指令的地址为15001
ret ;本条指令的地址为15002
模块A为主模块，模块B为目标模块，在执行call B指令的时候，函数调用栈区示意图如下（左边为调用前，右边为调用后），SP为栈顶指针。