42递归与递归基础.docVIP

1.求n! fac(n)=fac(n-1)*n n=1; fac(0)=1 n==0; 递推 #include stdio.h void main() { int m,i; float mul; printf(m=); scanf (%d,m); mul=1; for(i=1;i=m;i++) mul=mul*i; printf (%d! = %f \n,m,mul); } 函数 #include stdio.h float fac(int k) { int i; float mul; mul=1; for(i=1;i=k;i++) mul=mul*i; return(mul) } void main() { int m; printf(m=); scanf (%d,m); printf (%d! = %f \n,m,fac(m)); } 2）递归 #includestdio.h float fac(int m); main() { int n; printf(n=); scanf(%d,n); if(n=0) printf(n!=%e\n,fac(n)); else printf(error!\n); //完备性，防御性程序设计 } float fac(int m) { if(m=1) return(fac(m-1)*m); else return(1); } 递推（递归）表达式 一般情况 基元情况 区别： 1.递推： 自底向上 效率高 不易证正确性: Hoare公理，Dijstra最弱前置谓词 2.递归： 自顶向下 效率低：保留现场，参数传递。时间：重复计算，空间：栈溢出 易证明正确性：数学归纳法 2.求最大公约数 gcd(m,n)=gcd(n, m%n) m%n!=0; n else; 1）递推 #includestdio.h main() { int m,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\n,m0,n0,n); } 函数： #include stdio.h int gcd(int a,int b) { int t; while(a%b!=0) { t=a; a=b; b=t%n; } return(n); } void main() { int m,n ; printf(Input two integer:); scanf(%d,%d,m, n); printf(gcd(%d,%d) = %d \n,m,n,gcd(m,n)); } 2）递归 #include stdio.h int gcd(int a,int b) { if (a%b==0) return b ; else return gcd(b, a%b) ; } void main() { int m,n ; printf(Input two integer:); scanf(%d,%d,m, n); printf(gcd(%d,%d) = %d \n,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(n1) Hanoi(n-1, c, b, a) Move(n, a, b) If(n==1) F: main() Hanoi(n,a,c,b) Move(n, a, b) #includestdio.h void Hanoi(int n,char a,char c,char b); void Move(int n, char a, char b); main() { int n; printf(Input the number of disks:); scanf(%d,n); printf(Steps of moving