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

作者 | 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为栈顶指针。

执行完call B，就开始在模块B中执行，一直执行到ret返回指令，此时函数调用栈区示意图如下（左边为返回后，右边为返回前）。

执行完ret返回指令，将栈顶元素出栈送给程序计数器PC以供CPU继续执行主模块A中的剩余指令。

实际上，函数调用时入栈保护的不仅仅有主模块中调用指令之后的指令的地址，还有一些变量或者说数据，每个函数都有每个函数的局部变量，在主函数中调用子函数，主函数中的局部变量必须入栈保护，否则就会丢失。比如下面这个例子：

int add(int x,int y)

{

int a=x+1;

int b=y+1;

int c=a+b;

return c;

}

int main

{

int a=1,b=2;

int c=add(a,b);

printf(“%d+%d=%d ”,a,b,c);

return 0;

}

主函数和add函数里都有变量a和b，执行完add函数再返回到主函数中a的值必须还为1，b的值必须还为2，因此可以在调用add函数前先将主函数的所有变量（a和b）入栈保护，待执行完返回主函数时再出栈送给变量a和变量b。

递归函数的调用

递归函数的调用本质上也是函数的调用，只不过是自己在调用自己罢了。

以求斐波那契数列的项为例：

int fibonacci(int n)

{

if(n==1||n==2) //假设本条指令的地址为10000

return 1; //假设本条指令的地址为10001

int a=fibonacci(n-2); //假设本条指令的地址为10002

int b=fibonacci(n-1); //假设本条指令的地址为10003

int c=a+b; //假设本条指令的地址为10004

return c; //假设本条指令的地址为10005

}

如果进入函数的n是1或者是2，那么就直接返回1；

否则，就继续递归下去。

假设主函数调用斐波那契函数的指令的地址为15000，其下一条指令的地址为15001。

假设我们要求斐波那契数列的第5项，公式为

f(5)=f(3)+f(4)

=[f(1)+f(2)]+[f(2)+f(3)]

=[f(1)+f(2)]+[f(2)+[f(1)+f(2)]]

函数调用栈的示意图如下。

第一步，从主函数中进入斐波那契函数，传入的n为5。

第二步，斐波那契函数中执行到int a=fibonacci(n-2)，将下一条指令的地址压入栈，也就是将10003入栈，此时的n=5，将n=5压入数据栈，传入的n=3。

第三步，斐波那契函数中执行到int a=fibonacci(n-2)，将下一条指令的地址压入栈，也就是将10003入栈，此时的n=3，将n=3压入数据栈，传入的n=1。

第四步，此时n=1，可以直接返回1给上层的斐波那契函数的a，返回的同时出栈10003给程序计数器PC，出栈n=3给上一层斐波那契函数的n，回到上层的斐波那契函数。

第五步，执行程序计数器PC指向的指令（内存地址为10003的指令），也就是执行int b=fibonacci(n-1)，是一个函数调用，将下一条指令的地址压入栈，也就是将10004入栈，此时n=3，将n=3压入数据栈，此时a=1，将a=1压入数据栈，传入的n=2。

第六步，此时n=2，可以直接返回1给上层斐波那契函数的b，返回的同时出栈10004给程序计数器PC，出栈n=3给上一层斐波那契函数的n，出栈a=1给上一层斐波那契函数的a，回到了上层的斐波那契函数。

第七步，执行程序计数器PC指向的指令（内存地址为10004的指令），也就是执行int c=a+b，然后顺序执行一直到返回，返回2给上一层斐波那契函数的a，返回的同时出栈10003给程序计数器PC，出栈n=5给上一层的斐波那契函数的n，回到上层的斐波那契函数。

f(5)=f(3)+f(4)

=[f(1)+f(2)]+[f(2)+f(3)]

=[f(1)+f(2)]+[f(2)+[f(1)+f(2)]]

此时红色部分已通过递归计算完成。

第八步，执行程序计数器PC指向的指令（内存地址为10003的指令），也就是执行int b=fibonacci(n-1)，是一个函数调用，将下一条指令的地址压入栈，也就是将10004入栈，此时n=5，将n=5压入数据栈，此时a=2，将a=2压入数据栈，传入的n=4。

第九步，斐波那契函数中执行到int a=fibonacci(n-2)，将下一条指令的地址压入栈，也就是将10003入栈，此时的n=4，将n=4压入数据栈，传入的n=2。

第十步，此时n=2，可以直接返回1给上层的斐波那契函数的a，返回的同时出栈10003给程序计数器PC，出栈n=4给上一层斐波那契函数的n，回到上层的斐波那契函数。

第十一步，执行程序计数器PC指向的指令（内存地址为10003的指令），也就是执行int b=fibonacci(n-1)，是一个函数调用，将下一条指令的地址压入栈，也就是将10004入栈，此时n=4，将n=4压入数据栈，此时a=1，将a=1压入数据栈，传入的n=3。

第十一步，斐波那契函数中执行到int a=fibonacci(n-2)，将下一条指令的地址压入栈，也就是将10003入栈，此时的n=3，将n=3压入数据栈，传入的n=1。

第十二步，此时n=1，可以直接返回1给上层的斐波那契函数的a，返回的同时出栈10003给程序计数器PC，出栈n=3给上一层斐波那契函数的n，回到上层的斐波那契函数。

第十三步，执行程序计数器PC指向的指令（内存地址为10003的指令），也就是执行int b=fibonacci(n-1)，是一个函数调用，将下一条指令的地址压入栈，此时n=3，将n=3压入数据栈，此时a=1，将a=1压入数据栈，传入的n=2。

第十四步，此时n=2，可以直接返回1给上层的斐波那契函数的b，返回的同时出栈10004给程序计数器PC，出栈n=3给上一层斐波那契函数的n，出栈a=1给上一层斐波那契函数的a，回到上层的斐波那契函数。

第十五步，执行程序计数器PC指向的指令（内存地址为10004的指令），也就是执行int c=a+b，然后顺序执行一直到返回，返回2给上层斐波那契函数的b，返回的同时出栈10004给程序计数器PC，出栈n=4给上一层的斐波那契函数的n，回到上层的斐波那契函数。

第十六步，执行程序计数器PC指向的指令（内存地址为10004的指令），也就是执行int c=a+b，然后顺序执行一直到返回，返回3给上层斐波那契函数的b，返回的同时出栈10004给程序计数器PC，出栈n=5给上一层的斐波那契函数的n，出栈a=2给上一层的斐波那契函数的a，回到上层的斐波那契函数。

f(5)=f(3)+f(4)

=[f(1)+f(2)]+[f(2)+f(3)]

=[f(1)+f(2)]+[f(2)+[f(1)+f(2)]]

此时红色部分已通过递归计算完成。

第十七步，执行程序计数器PC指向的指令（内存地址为10004的指令），也就是执行int c=a+b，然后顺序执行一直到返回，返回5给上层斐波那契函数的接收者，返回的同时出栈15001给程序计数器PC，出栈主函数中的数据（未体现在图中），回到主函数。

此时斐波那契第五项计算完成。

后记

到了揭晓为什么会爆栈的时刻了，内存中实现函数调用的栈区的大小是有限的，如果递归层数太深，入栈的内容越来越多，甚至出现只入栈不出栈的情况（还没有符合返回条件执行到返回指令栈就满了），如此进行下去，栈满、栈溢出、爆栈只是时间问题，因此在实际项目应用中，如果不能估算出递归的深度，函数递归就要慎用了。

本文虽以斐波那契数列为例介绍函数递归调用的底层原理，但在真正的面试中如果面试官问到了斐波那契数列相关的问题，还是不要给面试官回答一个递归的解法，原因之一就是当n非常大的时候容易爆栈，原因之二就是文章开头说的会产生大量的重复计算。在这里我给大家再提一种解法，就是动态规划（DP）解法。不要一看到动态规划就害怕，斐波那契数列的动态规划解法还是很好理解的。先开一个大一些的数组f。

int fibonacci(int n)

{

f[1]=1,f[2]=1;

for(int i=3;i<=n;i++)

{

f[i]=f[i-2]+f[i-1];

}

return f[n];

}

这样无非是把递归变成了循环，但优点是不会出现重复计算。

简单的递归实现求斐波那契数列项的算法底层之复杂是我没有想象到的，直到一张图一张图亲手画出来我才大吃一惊，在这里我要感谢底层硬件工程师的辛勤付出，没有他们为我们布线铺路，我们是无法使用高级语言轻松编程的。

本文的介绍本着一切从简、方便理解的原则，可能有些地方与实际情况有出入，但是基本思想是一样的。如有不当之处，还请大家批评指正。