C语言递归课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,7.6 函数的递归调用,在调用一个函数的过程中又出现,直接或间接,地调用该函数本身,，称为函数的递归调用。语言的特点之一就在于允许函数的递归调用。例如：,int,f（,int,x）,int,y，,；,f（y）；,return（2*,）；,在调用函数,f,的过程中，又要调用,f,函数，这是,直接调用本函数,，见图7.9。下面是间接调用本函数。,在调用,f1,函数过程中要调用,f2,函数，而在调用,f2,函数过程中又要调用,f1,函数，这两种递归调用都是无终止的自身调用。显然，程序中不应出现这种无终止的递归调用，而只应出现有限次数的、有终止的递归调用，这可以用,if,语句来控制，只有在某一条件成立时才继续执行递归调用，否则就不再继续。,例7.7 有5个人坐在一起，问第5个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第3个人，又说比第2个人大2岁。问第2个人，说比第1个人大2岁。最后问第1个人，他说是10岁。请问第5个人多大。显然，这是一个递归问题。要求第5个人的年龄，就必须先知道第4个人的年龄，而第4个人的年龄也不知道，要求第4个人的年龄必须先知道第3个人的年龄，而第3个人的年龄又取决于第2个人的年龄，第2个人的年龄取决于第1个人的年龄。而且每一个人的年龄都比其前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（n1）,age（n1）2 （n1）,可以看到，当,n1,时，求第,n,个人的年龄的公式是相同的。因此可以用一个函数表示上述关系。图7.11表示求第5个人年龄的过程。,图,7.11,从图可知，求解可分成两个阶段：第一阶段是“回推”，即将第,n,个人的年龄表示为第（,n1）,个人年龄的函数，而第（,n1）,个人的年龄仍然不知道，还要“回推”到第（,n2）,个人的年龄直到第1个人年龄。此时,age（1）,已知，不必再向前推了。,然后开始第二阶段，采用递推方法，从第1个人的已知年龄推算出第2个人的年龄（12岁），从第2个人的年龄推算出第3个人的年龄（14岁）一直推算出第5个人的年龄（18岁）为止。也就是说，一个递归的问题可以分为“回推”和“递推”两个阶段。要经历许多步才能求出最后的值。显而易见，如果要求递归过程不是无限制进行下去，必须具有一个结束递归过程的条件。例如，,age（1）10，,就是使递归结束的条件。,#,include,int,age(,int,n),int,c;,if(n=1),c=10;,else,c=age(n-1)+2;,return(c);,void main(),printf,(%dn,age(5);,main,函数中只有一个语句。,图,7.12,从图7.12可以看到：,age,函数共被调用5次，即,age（5）、age（4）、age（3）、age（2）、age（1）。,其中,age（5）,是,main,函数调用的，其余4次是在,age,函数中调用的，即递归调用4次。请读者仔细分析调用的过程。应当强调说明的是在某一次调用,age,函数时并不是立即得到,age（n）,的值，而是一次又一次地进行递归调用，到,age（1）,时才有确定的值，然后再递推出,age（2）、age（3）、age（4）、age（5）。,请读者将程序和图7.11、图7.12结合起来认真分析。,例7.8用递归方法求,n！。,求,n！,也可以用递归方法，即5！等于4！5，而4！3！41！1。可用下面的递归公式表示：,n！1（n0，1）,n（n1）！（n1）,#,include,float,fac,(,int,n),float f;,if(n0),printf,(n0，data error！);,f=-1;,else,if(n=0|n=1),f=1;,else,f=,fac,(n-1)*n;,return(f);,void main(),int,n;,float y;,printf,(input a integer);,scanf,(%d,y=,fac,(n);,printf,(%d!=%15.0fn,n,y);,例7.9,hanoi,（,汉诺）塔问题。这是一个古典的数学,问题，是一个只有用递归方法（而不可能用其他方法）解决的问题。问题是这样的：古代有一个梵塔，塔内有3个座,A、B、C，,开始时座上有64个盘子，盘子大小不等，大的在下，小的在上。有一个老和尚想把这64个盘子从座移到座，但每次只允许移动一个盘，且在移动过程中每3个座上都始终保持大盘在下，小盘在上。在移动过程中可以利用座，要求编程序打印出移动的步骤。,(1)命令第2个和尚将63个盘子从,A,座移到,B,座；,(2)自己将1个盘子（最底下的、最大的盘子）从,A,座移到,C,座；,(3)命令第2个和尚将63个盘子从,B,座移到,C,座。,至此，全部任务完成了。这就是递归方法。但是，有一个问题实际上未解决：第2个和尚怎样才能将63个盘子从,A,座移到,B,座？为了解决将63个盘子从,A,座移到,B,座，第2个和尚又想：如果有人能将62个盘子从一个座移到另一座，我就能将63个盘子从,A,座移到,B,座，他是这样做的：,(1)命令第3个和尚将62个盘子从,A,座移到,C,座；,(2)自己将1个盘子从,A,座移到,B,座；,(3)命令第3个和尚将62个盘子从,C,座移到,B,座。,再进行一次递归。如此“层层下放”，直到后来找到第63个和尚，让他完成将2个盘子从一个座移到另一座，进行到此，问题就接近解决了。最后找到第64个和尚，让他完成将1个盘子从一个座移到另一座，至此，全部工作都已落实，都是可以执行的。可以看出，递归的结束条件是最后一个和尚只需移一个盘子。否则递归还要继续进行下去。,应当说明，只有第64个和尚的任务完成后，第63个和尚的任务才能完成。只有第2到第64个和尚任务完成后，第1个和尚的任务才能完成。,我们先分析将座上3个盘子移到座上的过程：,(1)将座上2个盘子移到座上（借助）；,(2)将座上1个盘子移到座上；,(3)将座上2个盘子移到座上（借助）。,其中第2步可以直接实现。第1步又可用递归方法分解为：,11将上1个盘子从移到；,12将上1个盘子从移到；,13将上1个盘子从移到。,第3步可以分解为：,31将上1个盘子从移到上；,32将上1个盘子从移到上；,33将上1个盘子从移到上。,将以上综合起来，可得到移动3个盘子的步骤为,，。,共经历7步。由此可推出：移动,n,个盘子要经历2,n,-1,步。如移4个盘子经历15步，移5个盘子经历31步，移64个盘子经历2,64,-1步。,由上面的分析可知：将,n,个盘子从座移到座可以分解为以下3个步骤：,(1)将上,n1,个盘借助座先移到座上。,(2)把座上剩下的一个盘移到座上。,(3)将,n1,个盘从座借助于座移到座上。,上面第1步和第3步，都是把,n1,个盘从一个座移到另一个座上，采取的办法是一样的，只是座的名字不同而已。为使之一般化，可以将第1步和第3步表示为：,#,include/*,将,n,个盘从,one,座借助,two,座，移到,three,座*/,void,hanoi,(,int,n,char one,char two,char three),if(n=1),printf,(%c-%cn,one,three);,else,hanoi,(n-1,one,three,two);,printf,(%c-%cn,one,three);,hanoi,(n-1,two,one,three);,void main(),int,m;,printf,(input the number of,diskes,：);,scanf,(%d,printf,(The step to moving%3d,diskes,：n,m);,hanoi,(m,a,b,c);,#,include/,方法2,void move(char x,char y),printf,(%c%cn,x,y);,void,hanoi,(,int,n,char one,char two,char three),/*,将,n,个盘从,one,座借助,two,座，移到,three,座*/,if(n=1)move(one,three);,else,hanoi,(n-1,one,three,two);,move(one,three);,hanoi,(n-1,two,one,three);,void main(),int,m;,printf,(input the number of,diskes,：);,scanf,(%d,printf,(The step to moving%3d,diskes,：n,m);,hanoi,(m,a,b,c);,方法2结果为：,input the number of,diskes,：3,The step to moving 3,diskes,ac,ab,cb,ac,ba,bc,ac,方法1结果为：,input the number of,diskes,：3,The step to moving 3,diskes,：,a-c,a-b,c-b,a-c,b-a,b-c,a-c,#,include/,利用递归完成求,n,的,m,次方,float f(,int,n,int,m),float y;,if(m=0),y=1;,else,if(m0),y=f(n,m-1)*n;,else,y=f(n,m+1)/n;,return y;,void main(),int,n=2;,int,m=-3;,printf,(,请输入,n,和,m,的值：);,scanf,(%d%d,printf,(n,的,m,次方为:%,f,f(n,m);,