4.2 递归与递归基础

《4.2 递归与递归基础》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.求n!fac(n)=fac(n-1)*nn>=1;fac(0)=1n==0;1）递推#includevoidmain(){intm,i;floatmul;printf("m=");scanf("%d",&m);mul=1;for(i=1;i<=m;i++)mul=mul*i;printf("%d!=%f",m,mul);}函数#includefloatfac(intk){inti;floatmul;mul=1;for(i=1;i<=k;i++)mul=mul*i;return(mul)}voidmain(){intm;printf("m

2、=");scanf("%d",&m);printf("%d!=%f",m,fac(m));}2）递归#includefloatfac(intm);main(){intn;printf("n=");scanf("%d",&n);if(n>=0)printf("n!=%e",fac(n));elseprintf("error!");//完备性，防御性程序设计}floatfac(intm){if(m>=1)return(fac(m-1)*m);elsereturn(1);}递推（递归）表达式1.一般情况2.基元情况区别：1.递推：自底向上效率高不易证正确性

3、:Hoare公理，Dijstra最弱前置谓词2.递归：自顶向下效率低：保留现场，参数传递。时间：重复计算，空间：栈溢出易证明正确性：数学归纳法2.求最大公约数gcd(m,n)=gcd(n,m%n)m%n!=0;nelse;1）递推#includemain(){intm,n,t,m0,n0;printf("m,n");scanf("%d%d",&m,&n);m0=m;n0=n;while(m%n!=0){t=m;m=n;n=t%n;}printf("gcd(%d,%d)=%d",m0,n0,n);}函数：#includeintgcd(inta

4、,intb){intt;while(a%b!=0){t=a;a=b;b=t%n;}return(n);}voidmain(){intm,n;printf("Inputtwointeger:");scanf("%d,%d",&m,&n);printf("gcd(%d,%d)=%d",m,n,gcd(m,n));}2）递归#includeintgcd(inta,intb){if(a%b==0)returnb;elsereturngcd(b,a%b);}voidmain(){intm,n;printf("Inputtwointeger:");scanf("%d,%

5、d",&m,&n);printf("gcd(%d,%d)=%d",m,n,gcd(m,n));}3.Hanoi塔问题（地球末日问题）1844亿亿次，每次0.01秒，计60亿年P:Hanoi塔问题A:Hanoi(n,a,b,c)=Hanoi(n-1,a,c,b)Move(n,a,b)if(n>1)Hanoi(n-1,c,b,a)Move(n,a,b)If(n==1)F:main()Hanoi(n,a,c,b)Move(n,a,b)#includevoidHanoi(intn,chara,charc,charb);voidMove(intn,chara,char

6、b);main(){intn;printf("Inputthenumberofdisks:");scanf("%d",&n);printf("Stepsofmoving%ddisksfromAtoBbymeansofC:",n);Hanoi(n,'A','B','C');}voidHanoi(intn,chara,charc,charb){if(n==1)Move(n,a,b);else{Hanoi(n-1,a,c,b);Move(n,a,b);Hanoi(n-1,c,b,a);}}voidMove(intn,chara,charb){printf("Move%d:form%

7、cto%c",n,a,b);}一致性：函数先声明再使用两种声明方法NP完全问题1.P多项式问题，如求1-n以内素数O(n*sqrt(n))。易解2.NP非多项式问题，指数问题：O(2^n),O(n!)。难解应用，密码前面两类称为可解（计算）的，图灵机或原始递归函数可解（计算）。P=NP?问题是计算机科学理论皇冠上的明珠。3.不可解（计算）问题。该问题的突破要依靠：电子->量子或分子计算机