有几个网站打不开,wordpress网站打包app,惠州建站平台,企业网站建设定制作者 | Cooper Song责编 | Elle出品 | 程序人生(ID#xff1a;coder_life)我猜#xff0c;大多数程序员第一次接触函数的递归调用都是在算斐波那契数列某项值的时候#xff0c;这是函数递归调用最常见的应用之一。规定第一项和第二项为1#xff0c;后面的项#xff0c;每一…作者 | Cooper Song责编 | Elle出品 | 程序人生(IDcoder_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语言为例有头文件只有引用了这个头文件你才能使用scanf和printf还有头文件只有引用了这个头文件你才能直接调用strlen函数得到字符串的大小。所谓程序的链接就是将整个程序的所有目标模块(比如程序员自己写的头文件和函数)以及其他所需要的库函数装配成一个完整的装入模块。原来每个模块都有每个模块的逻辑地址经过链接后形成了统一的从0开始的逻辑地址如下图所示。如何理解模块看上图大概就有了概念一个函数就是一个模块。程序的装入(Load)学过计算机组成原理的同学都知道在计算机中有个部件叫程序计数器(Program Counter简称PC)它存放的是程序要执行的下一条指令的地址CPU要到内存当中去取指令取到CPU中进行译码分析然后执行。程序原本存储在磁盘上因此只经过链接还不能运行还需要装入主存(内存)CPU通过PC提供的线索到内存中去取指令如此循环往复程序才得以运行下去。虽然程序的第一条指令的逻辑地址是0但它装入内存时在内存中的地址可不是0因为内存中的低地址是留给系统使用的也就是系统区比系统区的地址高的空间才是留给用户使用的也就是用户区。虽然装入内存后其地址不再是从0开始但其相对地址是不变的将上面链接好的装入模块装入内存内存空间示意图如下。函数的调用所谓函数的调用就是程序原本在主模块中顺序执行遇到调用指令暂时到别的模块执行在别的模块执行完后再返回主模块的下一条指令继续执行如下图所示。为什么可以执行着执行着就跳到别的模块执行了又为什么在别的模块执行完了又回到原来的模块执行了呢之所以能跳到别的模块执行是因为函数调用指令就指明了目标模块的首地址将目标模块的首地址传送给了程序计数器PC就中断了程序的顺序执行然后进入目标模块执行。之所以执行完子模块还能回到主模块中执行是因为内存中有一个专门实现函数调用的栈区在执行调用指令的时候就将主模块调用指令之后的指令的地址入了栈当子模块执行到返回指令的时候再出栈将栈顶元素(也就是主模块中要执行的下一条指令的地址)传给PC程序的执行就又回到了主模块。假设模块A中的指令是add ax,bx ;本条指令的地址为10000call B ;调用模块B本条指令的地址为10001mov dx,ax ;本条指令的地址为10002假设模块B中的指令是sub cx,dx ;本条指令的地址为15000mov bx,cx ;本条指令的地址为15001ret ;本条指令的地址为15002模块A为主模块模块B为目标模块在执行call B指令的时候函数调用栈区示意图如下(左边为调用前右边为调用后)SP为栈顶指针。执行完call B就开始在模块B中执行一直执行到ret返回指令此时函数调用栈区示意图如下(左边为返回后右边为返回前)。执行完ret返回指令将栈顶元素出栈送给程序计数器PC以供CPU继续执行主模块A中的剩余指令。实际上函数调用时入栈保护的不仅仅有主模块中调用指令之后的指令的地址还有一些变量或者说数据每个函数都有每个函数的局部变量在主函数中调用子函数主函数中的局部变量必须入栈保护否则就会丢失。比如下面这个例子int add(int x,int y){int ax1;int by1;int cab;return c;}int main{int a1,b2;int cadd(a,b);printf(“%d%d%d ”,a,b,c);return 0;}主函数和add函数里都有变量a和b执行完add函数再返回到主函数中a的值必须还为1b的值必须还为2因此可以在调用add函数前先将主函数的所有变量(a和b)入栈保护待执行完返回主函数时再出栈送给变量a和变量b。递归函数的调用递归函数的调用本质上也是函数的调用只不过是自己在调用自己罢了。以求斐波那契数列的项为例int fibonacci(int n){if(n1||n2) //假设本条指令的地址为10000return 1; //假设本条指令的地址为10001int afibonacci(n-2); //假设本条指令的地址为10002int bfibonacci(n-1); //假设本条指令的地址为10003int cab; //假设本条指令的地址为10004return 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 afibonacci(n-2)将下一条指令的地址压入栈也就是将10003入栈此时的n5将n5压入数据栈传入的n3。第三步斐波那契函数中执行到int afibonacci(n-2)将下一条指令的地址压入栈也就是将10003入栈此时的n3将n3压入数据栈传入的n1。第四步此时n1可以直接返回1给上层的斐波那契函数的a返回的同时出栈10003给程序计数器PC出栈n3给上一层斐波那契函数的n回到上层的斐波那契函数。第五步执行程序计数器PC指向的指令(内存地址为10003的指令)也就是执行int bfibonacci(n-1)是一个函数调用将下一条指令的地址压入栈也就是将10004入栈此时n3将n3压入数据栈此时a1将a1压入数据栈传入的n2。第六步此时n2可以直接返回1给上层斐波那契函数的b返回的同时出栈10004给程序计数器PC出栈n3给上一层斐波那契函数的n出栈a1给上一层斐波那契函数的a回到了上层的斐波那契函数。第七步执行程序计数器PC指向的指令(内存地址为10004的指令)也就是执行int cab然后顺序执行一直到返回返回2给上一层斐波那契函数的a返回的同时出栈10003给程序计数器PC出栈n5给上一层的斐波那契函数的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 bfibonacci(n-1)是一个函数调用将下一条指令的地址压入栈也就是将10004入栈此时n5将n5压入数据栈此时a2将a2压入数据栈传入的n4。第九步斐波那契函数中执行到int afibonacci(n-2)将下一条指令的地址压入栈也就是将10003入栈此时的n4将n4压入数据栈传入的n2。第十步此时n2可以直接返回1给上层的斐波那契函数的a返回的同时出栈10003给程序计数器PC出栈n4给上一层斐波那契函数的n回到上层的斐波那契函数。第十一步执行程序计数器PC指向的指令(内存地址为10003的指令)也就是执行int bfibonacci(n-1)是一个函数调用将下一条指令的地址压入栈也就是将10004入栈此时n4将n4压入数据栈此时a1将a1压入数据栈传入的n3。第十一步斐波那契函数中执行到int afibonacci(n-2)将下一条指令的地址压入栈也就是将10003入栈此时的n3将n3压入数据栈传入的n1。第十二步此时n1可以直接返回1给上层的斐波那契函数的a返回的同时出栈10003给程序计数器PC出栈n3给上一层斐波那契函数的n回到上层的斐波那契函数。第十三步执行程序计数器PC指向的指令(内存地址为10003的指令)也就是执行int bfibonacci(n-1)是一个函数调用将下一条指令的地址压入栈此时n3将n3压入数据栈此时a1将a1压入数据栈传入的n2。第十四步此时n2可以直接返回1给上层的斐波那契函数的b返回的同时出栈10004给程序计数器PC出栈n3给上一层斐波那契函数的n出栈a1给上一层斐波那契函数的a回到上层的斐波那契函数。第十五步执行程序计数器PC指向的指令(内存地址为10004的指令)也就是执行int cab然后顺序执行一直到返回返回2给上层斐波那契函数的b返回的同时出栈10004给程序计数器PC出栈n4给上一层的斐波那契函数的n回到上层的斐波那契函数。第十六步执行程序计数器PC指向的指令(内存地址为10004的指令)也就是执行int cab然后顺序执行一直到返回返回3给上层斐波那契函数的b返回的同时出栈10004给程序计数器PC出栈n5给上一层的斐波那契函数的n出栈a2给上一层的斐波那契函数的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 cab然后顺序执行一直到返回返回5给上层斐波那契函数的接收者返回的同时出栈15001给程序计数器PC出栈主函数中的数据(未体现在图中)回到主函数。此时斐波那契第五项计算完成。后记到了揭晓为什么会爆栈的时刻了内存中实现函数调用的栈区的大小是有限的如果递归层数太深入栈的内容越来越多甚至出现只入栈不出栈的情况(还没有符合返回条件执行到返回指令栈就满了)如此进行下去栈满、栈溢出、爆栈只是时间问题因此在实际项目应用中如果不能估算出递归的深度函数递归就要慎用了。本文虽以斐波那契数列为例介绍函数递归调用的底层原理但在真正的面试中如果面试官问到了斐波那契数列相关的问题还是不要给面试官回答一个递归的解法原因之一就是当n非常大的时候容易爆栈原因之二就是文章开头说的会产生大量的重复计算。在这里我给大家再提一种解法就是动态规划(DP)解法。不要一看到动态规划就害怕斐波那契数列的动态规划解法还是很好理解的。先开一个大一些的数组f。int fibonacci(int n){f[1]1,f[2]1;for(int i3;in;i){f[i]f[i-2]f[i-1];}return f[n];}这样无非是把递归变成了循环但优点是不会出现重复计算。简单的递归实现求斐波那契数列项的算法底层之复杂是我没有想象到的直到一张图一张图亲手画出来我才大吃一惊在这里我要感谢底层硬件工程师的辛勤付出没有他们为我们布线铺路我们是无法使用高级语言轻松编程的。本文的介绍本着一切从简、方便理解的原则可能有些地方与实际情况有出入但是基本思想是一样的。如有不当之处还请大家批评指正。
