您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

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

时间:2020-01-18 15:58:18  来源:  作者:
函数递归调用?看这文就够了

作者 | 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];

}

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

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

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



Tags:递归   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
一、问题提出问题:把m个苹果放入n个盘子中,允许有的盘子为空,共有多少种方法?注:5,1,1和1 5 1属同一种方法m,n均小于10二、算法分析设f(m,n) 为m个苹果,n个盘子的放法数目,则先对...【详细内容】
2021-11-17  Tags: 递归  点击:(49)  评论:(0)  加入收藏
对于二叉树,它的特点就是任何一个节点,左节点小于父节点、右节点大于父节点遍历二叉树有多种方式,如中序遍历、层序遍历、后序遍历,中序遍历的思路就是左-->父--->右的顺序,下面...【详细内容】
2021-11-02  Tags: 递归  点击:(39)  评论:(0)  加入收藏
正文在传统的后台管理系统里面经常会需要展示多级菜单关系,今天我们来学一下如何使用一条SQL语句展示多级菜单。现在我们有一张corpinfo单位表,里面有一个belong字段指向上级...【详细内容】
2020-12-25  Tags: 递归  点击:(227)  评论:(0)  加入收藏
1、引言今天我们来学习递归,如果单说学习算法, 递归并不能说是算法,而是一种编程的手法,为什么现在要学习这个呢?因为后面在学习其他算法时,要牵涉一些递归的调用方法,是为以后理解...【详细内容】
2020-09-21  Tags: 递归  点击:(50)  评论:(0)  加入收藏
前言递归,是一个非常重要的概念,也是面试中非常喜欢考的。因为它不但能考察一个程序员的算法功底,还能很好的考察对 时间空间复杂度 的理解和分析。本文只讲一题,也是几乎所有算...【详细内容】
2020-09-21  Tags: 递归  点击:(61)  评论:(0)  加入收藏
一、概述在本篇文章中,给大家介绍一下如何将文件进行zip压缩以及如何对zip包解压。所有这些都是使用Java提供的核心库 java.util.zip 来实现的。二、压缩文件首先我们来学...【详细内容】
2020-08-10  Tags: 递归  点击:(53)  评论:(0)  加入收藏
开始之前,首先来看一个通常我们不会以递归的形式思考的问题。假设我们想计算整数n的阶乘。n的阶乘可写作n!,其结果是1~n之间的各数之积。比如,4!=4&times;3&times;2&times;1。一...【详细内容】
2020-08-05  Tags: 递归  点击:(123)  评论:(0)  加入收藏
书上用了一个阶乘功能来演示递归:7.1 递归(阶乘)function factorial(number){ if (number <= 1){ return 1; }else { return number * arguments.calle...【详细内容】
2020-06-23  Tags: 递归  点击:(71)  评论:(0)  加入收藏
你对递归很纠结吗?虽然代码量少,理解起来太费劲?如果你这么想那就对了。因为我们人类的思维方式和递归的实现逻辑是有冲突的!我们想问题根本不那么想。可是程序员面试不得不准...【详细内容】
2020-06-21  Tags: 递归  点击:(116)  评论:(0)  加入收藏
比如我需要将 jpg 结尾的图片文件修改为 png 结尾的如果能用rename命令,运行下面的find . -name &#39;*.jpg&#39; -exec rename .jpg .png {} +如果不能用rename命令,使用下...【详细内容】
2020-06-19  Tags: 递归  点击:(92)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(11)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(22)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(14)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条