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

文章插图
第十步，此时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];}这样无非是把递归变成了循环，但优点是不会出现重复计算。
简单的递归实现求斐波那契数列项的算法底层之复杂是我没有想象到的，直到一张图一张图亲手画出来我才大吃一惊，在这里我要感谢底层硬件工程师的辛勤付出，没有他们为我们布线铺路，我们是无法使用高级语言轻松编程的。
本文的介绍本着一切从简、方便理解的原则，可能有些地方与实际情况有出入，但是基本思想是一样的。如有不当之处，还请大家批评指正。