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

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

时间: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:递归   点击:()  评论:()
声明:本站部分内容来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除,谢谢。
▌相关评论
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表
▌相关推荐
1、引言今天我们来学习递归,如果单说学习算法, 递归并不能说是算法,而是一种编程的手法,为什么现在要学习这个呢?因为后面在学习其他算法时,要牵涉一些递归的调用方法,是为以后理解...【详细内容】
2020-09-21   递归  点击:(10)  评论:(0)  加入收藏
前言递归,是一个非常重要的概念,也是面试中非常喜欢考的。因为它不但能考察一个程序员的算法功底,还能很好的考察对 时间空间复杂度 的理解和分析。本文只讲一题,也是几乎所有算...【详细内容】
2020-09-21   递归  点击:(6)  评论:(0)  加入收藏
一、概述在本篇文章中,给大家介绍一下如何将文件进行zip压缩以及如何对zip包解压。所有这些都是使用Java提供的核心库 java.util.zip 来实现的。二、压缩文件首先我们来学...【详细内容】
2020-08-10   递归  点击:(3)  评论:(0)  加入收藏
开始之前,首先来看一个通常我们不会以递归的形式思考的问题。假设我们想计算整数n的阶乘。n的阶乘可写作n!,其结果是1~n之间的各数之积。比如,4!=4&times;3&times;2&times;1。一...【详细内容】
2020-08-05   递归  点击:(4)  评论:(0)  加入收藏
书上用了一个阶乘功能来演示递归:7.1 递归(阶乘)function factorial(number){ if (number <= 1){ return 1; }else { return number * arguments.calle...【详细内容】
2020-06-23   递归  点击:(12)  评论:(0)  加入收藏
你对递归很纠结吗?虽然代码量少,理解起来太费劲?如果你这么想那就对了。因为我们人类的思维方式和递归的实现逻辑是有冲突的!我们想问题根本不那么想。可是程序员面试不得不准...【详细内容】
2020-06-21   递归  点击:(8)  评论:(0)  加入收藏
比如我需要将 jpg 结尾的图片文件修改为 png 结尾的如果能用rename命令,运行下面的find . -name &#39;*.jpg&#39; -exec rename .jpg .png {} +如果不能用rename命令,使用下...【详细内容】
2020-06-19   递归  点击:(12)  评论:(0)  加入收藏
作者 | Cooper Song责编 | Elle出品 | 程序人生(ID:coder_life)我猜,大多数程序员第一次接触函数的递归调用都是在算斐波那契数列某项值的时候,这是函数递归调用最常见的应用之一...【详细内容】
2020-01-18   递归  点击:(13)  评论:(0)  加入收藏
1.迭代是人,递归是神!从“编程之美”的角度看,可以借用一句非常经典的话:“迭代是人,递归是神!”来从宏观上对二者进行把握。从概念上讲,递归就是指程序调用自身的编程思想,即一个函...【详细内容】
2019-12-25   递归  点击:(29)  评论:(0)  加入收藏
递归是算法中一种非常重要的思想,应用也很广,小到阶乘,再在工作中用到的比如统计文件夹大小,大到 Google 的 PageRank 算法都能看到,也是面试官很喜欢的考点...【详细内容】
2019-12-16   递归  点击:(25)  评论:(0)  加入收藏
关系表:sys_functionid :主键idpid:父关系idOracle函数:start with&hellip;connect by&hellip;prior1.表数据select * from family; 2.查询自己和自己所有的后代select s.*from...【详细内容】
2019-12-13   递归  点击:(44)  评论:(0)  加入收藏
可能很多人在大一的时候,就已经接触了递归了,不过,我敢保证很多人初学者刚开始接触递归的时候,是一脸懵逼的,我当初也是,给我的感觉就是,递归太神奇了!...【详细内容】
2019-11-19   递归  点击:(25)  评论:(0)  加入收藏
对于很多人来说,都知道递归,也能看的懂递归,但在实际项目过程中,却不知道如何使用递归,这里给递归做个总结。递归的定义在数学与计算机科学中,递归(Recursion)是指在函数的定义中...【详细内容】
2019-10-14   递归  点击:(54)  评论:(0)  加入收藏
递归是一个神奇的算法,它是编程书籍中讲解的最尴尬部分。这些书籍通常会展示一个递归的阶乘实现,然后警告你,虽然它能运行但是它非常的慢并且可能会堆栈溢出而崩溃。虽然大家对...【详细内容】
2019-09-17   递归  点击:(32)  评论:(0)  加入收藏
递归是一个神奇的算法,它是编程书籍中讲解的最尴尬部分。这些书籍通常会展示一个递归的阶乘实现,然后警告你,虽然它能运行但是它非常的慢并且可能会堆栈溢出而崩溃。虽然大家对...【详细内容】
2019-09-16   递归  点击:(33)  评论:(0)  加入收藏
本文从一个递归栈溢出说起,像大家介绍一下如何使用尾调用解决这个问题,以及尾调用的原理,最后还提供一个解决方案的工具类,大家可以在工作中放心用起来。...【详细内容】
2019-09-10   递归  点击:(27)  评论:(0)  加入收藏
盗图前言最近准备面试 ,复习了一下数据结构 中的二叉树,整理了二叉树的前序、中序、后序、深度和广度遍历以及递归和非递归实现方法,如有好的方案大家可以一起讨论。前序遍历...【详细内容】
2019-09-09   递归  点击:(46)  评论:(0)  加入收藏
最近在实际工作中遇到一个需求,需要检测一个大文件夹下所有文件的更新状态,这个大文件夹下面包含了很多文件和文件夹,文件夹中又包含了很多文件和文件夹...... 类似下面这张图...【详细内容】
2019-08-16   递归  点击:(56)  评论:(0)  加入收藏
递归算法与动态规划算法是计算机程序设计、数据结构中常见算法。有些书籍教材中对递归算法与动态规划算法比较时,总是指出动态规划算法优于递归算法,在问题较为复杂时不建议使...【详细内容】
2019-06-19   递归  点击:(108)  评论:(0)  加入收藏
递归(recursion):程序调用自身的编程技巧。递归满足2个条件:1)有反复执行的过程(调用自身)2)有跳出反复执行过程的条件(递归出口)我这边自己的理解就是反复调用自己本身以前有写过简单...【详细内容】
2019-05-16   递归  点击:(149)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条