［推荐精品］递归与递归基础

《［推荐精品］递归与递归基础》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、intm;printf(nm=n);scanf(”％d”,&m);printf("%d!=%fH,m,fac(m));}2)递归#includefloatfac(intm);main(){intn;printf(Hn=n);scanf(n%dn,&n);if(n>=0)printf(nn!=%en,fac(n));elseprintf(nerror!n);〃完备性，防御性程序设计floatfac(intm)if(m>=l)retum(fac(m-1)*m);elsereturn(l);第1次调用第2次调用第3次调用第4次调

3、用fac(4)(4!=24)(3!=6)(2!=2)(11=1)图4・9例4.17的函数调用过程递推（递归）表达式1.一般情况2.基元情况区别：1•递推：口底向上效率高不易证正确性:Hoare公理，Dijstra最弱前置谓词2•递归：自顶向下效率低：保留现场，参数传递。时间：重复计算，空间：栈溢出易证明止确性：数学归纳法2•求最大公约数gcd(m,n)=gcd(n,m%n)m%n!=O;nelse;1)递推#includemain(){intm,n,t,mO,nO;printf(Hm,nn);scanf(n%d%dn,&m,&n);m

4、O=m;nO=n;while(m%n!=O){t=m;m=n;n=t%n;}printf(ngcd(%d,%d)=%d",mO,nO,n);函数:#includeintgcd(inta,intb){intt;while(a%b!=O){t=a；a=b;b=t%n;}return(n);}voidmain(){intm,n;printf(nInputtwointeger:11);scanf(H%d,%dn,&m,&n);printf(ngcd(%d,%d)=%d",m,n,gcd(m,n));}2)递归#include

5、o.h>intgcd(inta,intb){if(a%b==0)returnb;elsereturngcd(b,a%b);}voidmain(){intm,n;printf(nInputtwointeger:11);scanf(H%d,%dH,&m,&n);printf(Hgcd(%d,%d)=%d'm,n,gcd(m,n));}1.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>l)sHanoi(n-

6、1,c,b,a)乂Move(n,a,b)If(n==l)F:main()Hanoi(n,a,c,b)Move(n,a,b)#includevoidHanoi(intn,chara,charc,charb);voidMove(intn,chara,charb);main()intn;printf(nInputthenumberofdisks:”)；scanf(n%dn,&n);printf("Stepsofmoving%ddisksfromAtoBbymeansofC:n,n);Hanoi(n,A,E,C);}voidHanoi(i

7、ntn,chara,charc,charb){if(n==l)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(nMove%d:form%cto%c",n,a,b);一致性:函数先声明再使用两种声明方法NP完全问题1.P多项式问题，如求l・n以内素数O(n*sqrt(n))0易解1.NP非多项式问题，指数问题：0(2An),O(n!)o难解应用，密码前面两类称为可解(计算)的，图灵机或原始递归函数可解(

8、计算)。P=NP?问题是计算机科学理论皇冠上的明珠。2.不可解(计算)问题。该问题的突破要依靠