函数嵌套调用和递归调用.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,C,语言程序设计,学习内容：,函数的嵌套调用和递归调用,6.9,函数的嵌套调用和递归调用,引例,编程函数求解：,y=(x+y),2,!,然后调用函数求解,(2+3),2,！以及,(3+4),2,！,要求：,1,、首先编写求和函数，求解,x+y,的和。,2,、编写函数求解,(,x+y,),的平方,(x+y),2,3,、编写函数求解,(x+y),2,！,main(),int,a,b,c,;,scanf(“%d,%d”,&a,&b,);,jc(,a,b,);,printf(“sum,is%d,c);,int,jc(int,k,int,j),int,z,m,i,s,=1;,sum(k,j);,pf(,z,);,for(i,=1;i=,m,;i,+),s=s*i;,return s;,int,sum(int,x,int,y),return(,x+y,);,int,pf(,int,h),return(h*h);,c=,z=,m=,6.9.1,函数的嵌套调用,C,语言中不允许嵌套的函数定义，各函数之间是平行的，不存在上一级函数和下一级函数的问题。,void print(),putchar,(*);,void,prnline,(,int,n),int,i;,for(i,=0;i=,n;i,+),putchar(n,);,C,语言允许在一个函数的定义中出现对另一个函数的,调用,(,使用,),。这样就出现了函数的嵌套调用，即在被使用函数中又调用其他函数。,#include,long,sum(int,a,int,b);,long,factorial(int,n);,main(),int,n1,n2;,long a;,scanf(%d,%d,a=,sum(n1,n2);,printf(a,=%,1d,a);,long,sum(,int,a,int,b,),long c1,c2;,factorial(a,);,factorial(b,);,return(c1+c2);,long,factorial(int,n),long,rtn,=1;,int,i;,for(i=1;i=n;i+),rtn,*=i;,return(rtn,);,long,sum(int,a,int,b);,long,factorial(int,n);,文件包含编译预处理命令,函数声明,函数定义,函数调用,函数调用,函数返回值,形参,实参,c1=,c2=,long,factorial(int,n),long,rtn,=1;,int,i;,for(i=1;i=n;i+),rtn,*=i;,return(rtn,);,例,2,求三个数中最大数和最小数的差值,#include,int,dif(int,x,int,y,int,z);,int,max(int,x,int,y,int,z);,int,min(int,x,int,y,int,z);,void main(),int,a,b,c,d,;,scanf(%d%d%d,&a,&b,&c,);,d=,dif(a,b,c,);,printf(Max,-Min=%,dn,d,);,int,min(int,x,int,y,int,z),int,r;,r=x,y?x:y,;,return(r,y?x:y,;,return(r,z?r:z,);,int,dif(int,x,int,y,int,z),return,max(x,y,z)-min(x,y,z,);,f(x+y)2,x+y (xy),其中：,f(t)=(1+e,-t,)/(1+e,t,),求,result=g(2.5,3.4),。,练习,练习,例,：编写求组合数的函数。,6.9.2,函数的递归调用,递归,:,一个函数直接或间接地使用自身。,1.,直接递归调用：,函数直接调用本身,2.,间接递归调用：,函数间接调用本身,int,f(int,x),int,y,z;,z=f(y);,.,return(2*z);,int,f1(int x),int,y,z;,z=f2(y);,.,return(2*z);,int,f2(int t),int,a,c;,c=f1(a);,.,return(3+c);,直接调用,间接调用,【,例,1】,有,5,个人，第,5,个人说他比第,4,个人大,2,岁，第,4,个人说他对第,3,个人大,2,岁，第,3,个人说他对第,2,个人大,2,岁，第,2,个人说他比第,1,个人大,2,岁，第,1,个人说他,10,岁。求第,5,个人多少岁。,通过分析，设计递归函数如下：,10 (n=1),age(n)=,age(n-1)+2 (n1),递归函数：,10 (n=1),age(n)=,age(n-1)+2 (n1),age(,int,n),int,c;,if(n=1)c=10;,else c=,age(n-1),+2;,return c;,main(),int,x;,x=,age(5);,printf(%d,x,);,程序如下：,请看看单步运行的情况,age(,5,),c=age(,4,)+2;,return c;,age(int,n),int,c;,if(n=1)c=10;,else c=,age(n-1),+2;,return c;,递归过程,跟踪分析：,age(,4,),c=age(,3,)+2;,return c;,age(,3,),c=age(,2,)+2;,return c;,age(,2,),c=age(,1,)+2;,return c;,age(,1,),c=,10,return c;,c=10,c=12,c=14,c=16,c=18,main(),int,x;,age(3);,printf(%d,x,);,age(,int,n ),int,c;,else,return c;,3,age(n-1),2,age(,int,n ),int,c;,else,return c;,2,age(n-1),1,age(,int,n ),int,c;,if(n=1)c=10;,return c;,1,c=,+2,+2,c=,x=,总结：递归算法,递归函数名,f(,参数,x),if(x=,初值,),/,递归结束的条件,结果,=,；,else,结果,=,含,f(x-1),的表达式；,返回结果（,return,）；,f(n,),f(n-1),main(),f(n),f(n-1),f(n-2),f(n-2),f(n-3),f(1,或者,0),f(0)=,),例,2,：用递归算法计算,n,！,n!=n*(n-1)!,(n-1)!=(n-1)*(n-2)!,.,5!=5*4!,4!=4*3!,3!=3*2!,2!=2*1!,1!=1,long,jc(int,n),long k;,if(n,=1)k=1;,else k=n*jc(n-1);,return k;,main(),long x;,x=jc(6);,printf(%ld,x,);,long,jc(int,n),long k;,int,i;,for(i,=1;i2,根据数学公式，很容易将,n,阶的问题转化成,n-1,阶和,n-2,阶的问题，即：,f(n)=f(n-1)+f(n-2),，,递归出口：,n=1,或者,n=2,。,程序如下：,#include,stdio.h,int,fib(int,n),if(n=1)|(n=2)return 1;,else return(fib(n-1)+fib(n-2);,main(),int,i;,printf(n,);,printf,(%d,fib(20);,例,4:,汉诺塔,(Hanoi),问题,B,C,问题,:,将,A,塔上,n,个盘子移至,C(,借助于,B),。,移动时,保证三个塔始终是大盘在下,小盘在上。,A,n,个盘子,必须用递归方式解决，将,n,阶问题转为,n-1,阶：,1),先将,A,塔,n,1,个盘子借助于,C,移至,B,上：,2),将,A,上剩下的一个移至,C,上.,3),将,B,上,n,1,个盘子借助于,A,移至,C,上.,可以看到:,1)、3)为同一问题,都为,n,1,个盘子借助于一个空塔移至另一塔上。,递归出口：,n=1,，此时,A,座上只有一个盘子，直接将其移动到,C,座上即可。,#include,stdio.h,void,move(int,n,char x,char y,char z),if(n=1),printf(%c,-%cn,x,z);,else,move(n-1,x,z,y);,/n-1,盘子已经到,y,上,printf(%c,-%cn,x,z);,move(n-1,y,x,z);,/y,上,n-1,盘子想办法放到,z,main(),int,n;,printf,(input the number of,diskes,:);,scanf(%d,&n,);,move(n,a,b,c);,运行情况如下：,input the number of diskes:3,A,C,A B,C B,A C,B A,B C,A C,B,A,C,A,C,A B,C B,A C,B A,B C,A C,练习,1,、用递归方法求和：,1,！,+2,！,+3,！,+4,！,+5,！,+n!,其中,n,的值由键盘输入。,2,、有,5,个人，第,5,个人说他的钱是第,4,个人的,2,倍还多,100,元，第,4,个人说他是第,3,个人的,2,倍还多,100,，第,3,个人说他是第,2,个人的,2,倍还多,100,，第,2,个人说他是第,1,个人的,2,倍还多,100,，第,1,个人说他,1000,元。求第,5,个人有多少钱。,