(6.29)--第28课（6.4节-递归函数）C语言程序设计.ppt

《(6.29)--第28课（6.4节-递归函数）C语言程序设计.ppt》由会员分享，可在线阅读，更多相关《(6.29)--第28课（6.4节-递归函数）C语言程序设计.ppt（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、递归函数函数函数的嵌套调用函数的嵌套调用l不允许嵌套定义函数，函数间的关系是平行的、独立的l允许嵌套调用，即在调用某函数过程中又调用另一函数main()main()调用函数调用函数a a结束结束a a函数函数b b函数函数调用函数调用函数b b【例1：】求三个数中最大数和最小数的差值#include#include int dif(int x,int y,int int dif(int x,int y,int z);z);int max(int x,int y,int int max(int x,int y,int z);z);int min(int x,int y,int int min(i

2、nt x,int y,int z);z);void main()void main()int a,b,c,d;int a,b,c,d;scanf(%d%d%d,&a,&b,&c);scanf(%d%d%d,&a,&b,&c);d=dif(a,b,c);d=dif(a,b,c);printf(Max-Min=%dn,d);printf(Max-Min=%dn,d);int dif(int x,int y,int z)int dif(int x,int y,int z)return return max(x,y,z)max(x,y,z)-min(x,y,z)min(x,y,z);int max(i

3、nt x,int y,int z)int max(int x,int y,int z)int r;int r;r=xy?x:y;r=xy?x:y;return(rz?r:z);return(rz?r:z);int min(int x,int y,int z)int min(int x,int y,int z)int r;int r;r=xy?x:y;r=xy?x:y;return(rz?r:z);return(r1#include int age(int n)int c;if(n=1)c=10;else c=2+age(n-1);return(c);void main()printf(“%d

4、n”,age(5);递归的本质递归的本质l将大问题的求解转化为较小问题的求解l持续不断的分解过程最终将问题化简成一个最基本的形式（该形式是一个已知解）条件成立，进行递归条件成立，进行递归 l用用ifif语句控制语句控制 条件不成立，结束递归条件不成立，结束递归解决无终止递归调用的方法是：确定好结束递归的条件【例3：】用递归方法计算n!分析4!=4*3*2*14!=4*3!3!=3*2!.递归公式n!n!=1 1 （n=0n=0或或1 1）n*n*(n-1)!(n-1)!（n1n1）#include long fac(int n)long f;if(n=0|n=1)f=1;else f=n*fa

5、c(n-1);return f;void main()printf(nt4!=%ldn,fac(4);f=fac(4);n=4if(n=0|n=1)f=1;else f=n*fac(n-1);fac(n-1);return(f)n=3if(n=0|n=1)f=1;else f=n*fac(n-1);fac(n-1);return(f)n=2if(n=0|n=1)f=1;else f=n*fac(n-1);fac(n-1);return(f)n=1if(n=0|n=1)f=1f=1;else f=n*fac(n-1);return(f)设设n=4n=44!递归结束条件递归结束条件244*3!6*

6、43*2!2*1!12*31*21【例4：】求两个整数的最大公约数求最大公约数可以采用辗转相除法int gcd(int a,int b)if(a%b=0)return b;return gcd(b,a%b);【例5：】使用递归算法生成斐波那契(Fibonacci)数列l递归公式：递归公式：f1=1 (n=1)f1=1 (n=1)f2=1 (n=2)f2=1 (n=2)f fn n=f=fn-1n-1+f+fn-2n-2 (n3)(n3)int fib(int n)int fib(int n)if(n=2)if(n1时1.1.利用塔座利用塔座Z Z为辅助塔座，将压在圆盘为辅助塔座，将压在圆盘n

7、n之上的之上的n-1n-1个盘从塔座个盘从塔座X X移到塔座移到塔座Y Y（与原问题类似）与原问题类似）2.2.将圆盘将圆盘n n从塔座从塔座X X移到塔座移到塔座Z Z3.3.利用塔座利用塔座X X为辅助塔座，将塔座为辅助塔座，将塔座Y Y上的上的n-1n-1个圆盘个圆盘移动到塔座移动到塔座Z Z（与原问题类似）与原问题类似）XYZXYZXYZXYZ汉诺塔问题汉诺塔问题设计lmove 函数：移动一个盘-把盘 n 从 s 塔移到 d 塔lhanoi 函数：移动n个盘的汉诺塔问题-把 n 个盘从 x 塔移到 z 塔，y 塔作为辅助塔void move(int n,char s,char d);v

8、oid move(int n,char s,char d);void hanoi(int n,char x,char y,char z);void hanoi(int n,char x,char y,char z);汉诺塔问题汉诺塔问题实现#include#include void move(int n,char s,char d);void move(int n,char s,char d);void hanoi(int n,char x,char y,char z);void hanoi(int n,char x,char y,char z);void main()void main()i

9、nt n;int n;printf(t Input the number of disks:);printf(t Input the number of disks:);scanf(%d,&n);scanf(%d,&n);hanoi(n,X,Y,Z);hanoi(n,X,Y,Z);void void hanoihanoi(int n,char x,char y,char z)(int n,char x,char y,char z)if(n=1)move(n,x,z);if(n=1)move(n,x,z);else else hanoi(n-1,x,z,y)hanoi(n-1,x,z,y);mo

10、ve(n,x,z);move(n,x,z);hanoi(n-1,y,x,z)hanoi(n-1,y,x,z);void void movemove(int n,char s,char d)(int n,char s,char d)printf(t%dt%c-%cn,n,s,d);printf(t%dt%c-%cn,n,s,d);利用塔座利用塔座Z Z为辅助塔座，将压在圆盘为辅助塔座，将压在圆盘n n之之上的上的n-1n-1个盘从塔座个盘从塔座X X移到塔座移到塔座Y Y；将圆盘将圆盘n n从塔座从塔座X X移到塔座移到塔座Z Z利用塔座利用塔座X X为辅助塔座，将塔座为辅助塔座，将塔座Y Y上的上的n-n-1 1个圆盘移动到塔座个圆盘移动到塔座Z Z谢谢西华大学