VB函数递归与调用.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,精选2021版课件,*,函数的递归调用,1,精选2021版课件,函数的递归调用,递归,:,一个函数直接或间接地使用自身。,1.,直接递归调用：,函数直接调用本身,2.,间接递归调用：,函数间接调用本身,2,精选2021版课件,情景,1,：,小时候，我们听过这样的故事：,从前有座山，山上有座庙，庙里有个老和尚给小和尚讲故事，讲的什么,故事,呢？,从前有座山，山上有座庙，庙里有个老和尚给小和尚讲故事，讲的什么,故事,呢？,从前有座山，山上有座庙，庙里有个老和尚给小和尚讲故事，讲的什么故事呢？,故事可以一直讲下去，每一个故事内容都相同，但却是,故事里的故事,。,程序设计中，函数,A,自己调用自己，称为,直接递归调用,。,3,精选2021版课件,情景,2,：,镜子,A,和镜子,B,相对放在一起，你会发现什么现象呢？,对了，我们会发现镜子,A,中有镜子,B,的映象，镜子,B,中又镜子,A,的映象，这样层层叠叠，无穷无尽。,A,B,在程序设计中，像这种函数,A,调用函数,B,函数,B,再反过来调用函数,A,的算法，称为,间接递归调用,。,4,精选2021版课件,递归算法的特点：,递归函数的执行过程比较复杂，往往都存在着连续的递归调用，其执行过程可分为,“递推”,和,“回归”,两个阶段，先是一次一次不断的递推过程，直到符合递推”结束条件，然后是一层一层的回归过程。,而其中的每一次递归调用，系统都要在栈中分配空间以保存该次调用的,返回地址、参数、局部变量,，因此在递推阶段，栈空间一直处于增长状态，然后进入回归阶段，栈空间反向依次释放。直到“递推”过程的终止，,在递归的执行过程中，递归结束条件非常重要，它控制“递推”过程的终止，在任何一个递归函数中，递归结束条件都是必不可少的，否则将会一直“递推”下去。导致无穷递归。,递归算法的缺点,：内存消耗巨大，且连续地调用和返回操作占用较多的,CPU,时间。,递归算法的优点,：算法描述简洁易懂。,5,精选2021版课件,思考如下问题：,例,1:,有,5,个人坐在一起,问第,5,个人多少岁,他说比第,4,个人大,2,岁,;,问第,4,个人岁数,他说比,第,3,个人大,2,岁,;,问第,3,个人,又说比第,2,个大,2,岁,;,问第,2,个人，说比第,1,个人大,2,岁；最后问第,1,个人，他说他,10,岁；请问第,5,个人多大,?,比她大,2,岁,比她大,2,岁,比她大,2,岁,比她大,2,岁,我,10,岁,6,精选2021版课件,分析,：要求第,5,个人的年龄，就必须先知道第,4,个人的年龄，而第,4,个人的年龄也不知道，要求第,4,个人的年龄必须先知道第,3,个人的年龄，而第,3,个人的年龄又取决于第,2,个人的年龄，第,2,个人的年龄取决于第,1,个人的年龄。而且每一个人的年龄都比其前,1,个人的年龄大,2,。第一个人的年龄已知，根据第一个人的年龄可依次求得第二、三、四、五个人的年龄。这就是一个递归问题。,而,每一个人的年龄都比其前,1,个人的年龄大,2,就是递归成立的条件，也就是,递归公式,。,age,（,5,）,=age,（,4,）,2,age,（,4,）,=age,（,3,）,2,age,（,3,）,=age(2,）,+2,age,（,2,）,age(1,）,2,age,（,1,）,10,可以用式子表述如下：,age,（,n,）,=10,（,n=1,）,age,（,n,）,=age,（,n-1)+2,（,n,1,）,可以看到，当,n,1,时，求第,n,个人的年龄的公式是相同的。因此可以用一个函数来表示上述关系，下图表示求第,5,个人年龄的过程。,7,精选2021版课件,age(5)age(5),=age(4)+2 =18,age(4)age(4),=age(3)+2 =16,age(3)age(3),=age(2)+2 =14,age(2)age(2),=age(1)+2 =12,age(1),=10,回推,递推,8,精选2021版课件,从图可知，求解可分成两个阶段：第一阶段是,“,回推,”,，即将第,n,个人的年龄表示为第（,n-1,）个人年龄的函数，而第（,n,一,1,）个人的年龄仍然不知道，还要,“,回推,”,到第（,n,一,2,）个人的龄,，直到第,1,个人的年龄。此时,age(1),已知，不必再向前推了。然后开始第二阶段，采用,递推,方法，从第,1,个人的已知年龄推算出第,2,个人的年龄（,12,岁），从第,2,个人的年龄推算出,3,个人的年龄（,14,岁）,，一直推算出第,5,个人的年龄（,18,岁）为止。也就是说，一个递归的题可以分为“,回推,”和“,递推,”,两个阶段。要经历许多步才能求出最后的值。显而易见，如果求递归过程不是无限制进行下去，必须具有一个结束递归过程的条件。,例如，,age,（,1,）,10,，就是递归结束的条件。,9,精选2021版课件,可以用一个函数来描述上述递归过程：,age,（,n,）,/*,求年龄的递归函数*,int n,；,int c,；,*,c,用来存放函数的返回值,if,（,n=1,）,c=10;,else c=age,（,n,一,1,）十,2,；,return,（,c),；,main,（）,/*,主函数*,printf,（,%d,，,age,（,5,）；,10,精选2021版课件,例题二,用递归方法求,n!,分析：假设,n=5,我们知道,5,！,=1*2*3*4*5=4,！*,5,4,！,=1*2*3*4=3,！*,4,3,！,=1*2*3=2,！*,3,2,！,=1*2=1,！*,2,1,！,=1,可用下面的递归公式表示,n!=1,（,n=1,）,n!=(n-1)!*n (n 1),11,精选2021版课件,“,回推”和“递推”,5,！,54,！,43,！,32,！,21,！,1,5,！,4,！,5,3,！,4,2,！,3,1,！,2,1,回,推,过,程,返回,1,返回,1,！,2,2,返回,2,！,3,6,返回,3,！,4,24,返回,4,！,5,120,终值,120,递,推,过,程,调用函数,函数返回值,12,精选2021版课件,递归法求,Fibonacci,数列,Fibonacci,数列,:1,1,2,3,5,8,13,迭代法求,Fibonacci,数列的前,20,项,#include,void main(),int i,f1=1,f2=1,f3;,printf(“%8d%8d”,f1,f2);,for(i=3;i1,F(n)=,递归的终止条件,递归公式,int,Fib(int n),if(n0),printf(“error!”);exit(-1);,else,if(n 1,）个盘子的汉诺塔，可分为三个步骤求解：,17,精选2021版课件,1.,将,A,针上,n-1,个盘子借助于,C,针移到,B,针,2.,把,A,针上剩下的一个盘子移到,C,针,3.,将,B,针上,n-1,个盘子借助于,A,针移到,C,针,显然，上述,1,3,两步具有与原问题相同的性质，只是在问题的规模上比原问题有所缩小，可用递归实现。,整理上述分析结果，把第一步作为递归结束条件，将第二步分析得到的算法作为递归算法，可以写出如下完整的递归算法描述：,定义一个函数,movedisk(int n,char fromneedle,char tempneedle,char toneedle),，该函数的功能是将,fromneedle,针上的,n,个盘子借助于,tempneedle,针移动到,toneedlee,针，这样移动,n,个盘子的递归算法描述如下：,18,精选2021版课件,movedisk(int n,char fromneedle,char tempneedle,char toneedle),if(n=1),将,n,号盘子从,one,针移到,three,针,;,esle,1.movedisk(n-1,fromneedle,toneedle,tempneedle),2.,将,n,号盘子从,fromneedle,针移到,toneedle,针,;,3.movedisk(n-1,tempneedle,fromneedle,toneedle),按照上述算法可编写出如下,C,语言程序：,19,精选2021版课件,#include,void main(),void movedisk(int n,char fromneedle,char,tempneedle,char toneedle);,int n;,printf(“Pleases input the number of diskes:”);,scanf(“%d”,printf(“The step moving diskes is:n”);,movedisk(n,A,B,C);,void movedisk(int n,char fromneedle,char tempneedle,char toneedle),if(n=1)printf(“%c,%cn”,fromneedle,toneedle);,else,movedisk(n-1,fromneedle,toneedle,tempneedle);,printf(“%c,%cn”,fromneedle,toneedle);,movedisk(n-1,tempneedle,fromneedle,toneedle);,20,精选2021版课件,以,N=3,为例,B,C,A,21,精选2021版课件,以,N=3,为例,第一步：A,C,B,C,A,22,精选2021版课件,以,N=3,为例,第二步：A,B,B,C,A,23,精选2021版课件,以,N=3,为例,第三步：,C,B,B,C,A,24,精选2021版课件,以,N=3,为例,第四步：,A,C,B,C,A,25,精选2021版课件,以,N=3,为例,第五步：,B,A,B,C,A,26,精选2021版课件,以,N=3,为例,第六步：,B,C,B,C,A,27,精选2021版课件,以,N=3,为例,第七步：,A,C,B,C,A,28,精选2021版课件,29,精选2021版课件,八皇后问题,问题描述：,会下国际象棋的人都很清楚：皇后可以在横竖斜线上不限步数地吃掉其他棋子，如何将,8,个皇后放在棋盘上（有,8*8,个方格），使他们谁也不能被吃掉！这就是著名的八皇后问题。对于某个满足要求的,8,皇后的摆放方法，定义一个皇后串,a,与之对应，即,a=b1b2,b8,，其中,bi,为相应摆法中第,i,行皇后所处的列数。已经知道,8,皇后问题一共有,92,组解（即,92,个、不同的皇后串）。给出一个数,b,，要求输出第,b,个串。串的比较是这样的：皇后串,x,置于皇后串,y,之前，当且仅当将,x,视为整数时比,y,小。,输入数据：,第一行是测试数据的组数,n,，后面跟着,n,行输入，每组测试数据占,1,行，包括一个正整数,b,（,1=b=92,）。,输出要求：,n,行，每行输出对应一个输入。输出应是一个正整数，是对应于,b,的皇后串。,输入样例：,2,1,92,输出样例：,15863724,30,精选2021版课件,解题思路：,1,、因为要求出,92,中不同的摆放方法中的任意一种，所有我们不妨把,92,中不同的摆放方法一次性求出来，存放在一个数组里。为求解这道题我们需要一个矩阵仿真棋盘，每次试放一个棋子时只能放在尚未被控制的格子上，一旦放置了一个新棋子，就在它所能控制的所有位置上设置标记，如此下去把八个棋子放好。完成一种摆放时，就要尝试下一种。若要按照字典序将可行摆放方法记录下来，就要按照一定的顺序进行尝试。也就是将第一个棋子按照从小到大的顺序尝试，对于第一个棋子的位置，将第二个棋子从可行的位置从小到大的顺序尝试；在第一和第二个棋子固定的情况下，将第三个棋子从可行的位置从小到大的顺序尝试；以此类推。,2,、首先，我们有一个,8*8,的矩阵仿真棋盘标识当前已经摆好的棋子所控制的区域。用一个,92,行每行,8,个元素的二维数组记录可行的摆放方法。用一个递归程序实现尝试摆放的过程。基本思想就是假设我们将第一个棋子摆好，并设置它的控制区域，则这个问题就变成了一个,7,皇后问题，用与,8,皇后同样的方法可以获得问题的求解。那我们就把重心放在如何摆放一个皇后棋子上，摆放的基本步骤是：从第,1,到第,8,个位置，顺序地尝试将棋子放置在每一个未被控制的位置，设置该棋子所控制的格子，将问题变成更小规模的问题向下递归，需要注意的是每次尝试一个新的未被控制的位置前，要将上一次尝试的位置所控制的格子复原。,31,精选2021版课件,#include,#include,int queenPlaces928;,int count=0;,int board88;,void putQueen(int ithQueen);/,递归函数,void main(),int n,i,j;,for(i=0;i8;i+),for(j=0;i8;j+),boardij=-1;,for(j=0;j92;j+),queenPlacesji=0;,putQueen(0);/,从第,0,个棋子开始摆放,scanf(“%d”,for(i=0;in;i+),int ith;,scanf(“%d”,&ith),for(j=0;j8;j+),printf(“%d”,queenPlacesithj);,printf(“n”);,32,精选2021版课件,void putQueen(int ithQueen),int i,k,r;,if(ithQueen=8),count+;,return;,for(i=0;i8;i+),if(boardiithQueen=-1),boardiithQueen=ithQueen;/,摆放皇后,/,将其后所有的摆放方法的,ith,个皇后都放在,i+1,的位置上,/,将,i,增加后，后面的第,ith,个皇后摆放方法后覆盖此时的设置,for(k=count;k92;k+),queenPlaceskithQueen=i+1;,/,设置控制范围,for(k=0;k8;k+),for(r=0;r8;r+),if(boardkr=-1)&,(k=i|r=ithQueen|abs(k-i)=abs(r-ithQueen),boardkr=ithQueen;/,向下级递归,putQueen(ithQueen+1);/,回溯，撤销控制范围,for(k=0;k8;k+),for(r=0;r8;r+),if(boardkr=ithQueen)boardkr=-1;,33,精选2021版课件,