42递归与递归基础

1、1 求 n!fac(n)=fac(n-1 )*nn>= 1;fac(o)=ln=0;1) 递推#include <stdio.h>void main() int m,i；float mul;printf(hm=n);scanf (”d”,&m);mul=l;for(i=l;i<=m;i+)mul=mul*i;printf (n%d! = %f n",m,mul);函数#include <stdio.h>float fac(int k) int i;float mul;mul=l;for(i=l;i<=k;i+)mul=mul*i;re

2、turn(mul)void main() int m;printf(nm=n); scanf (”d”,&m); printf ("%d! = %f nh,m,fac(m);2)递归#include<stdio.h>float fac(int m);main()int n;printf(hn=n);scanf(n%dn,&n);if(n>=0)printf(nn!=%enn,fac(n);elseprintf(nerror!nn); 完备性，防御性程序设计float fac(int m)if(m>=l) retum(fac(m-1)*m);el

3、se return(l);第1次调用第2次调用第3次调用第4次调用fac(4)(4! = 24)(3!=6)(2! = 2)(11= 1)图49例4.17的函数调用过程递推（递归）表达式1. 一般情况2. 基元情况区别：1递推：口底向上效率高不易证正确性:hoare公理，dijstra最弱前置谓词2 递归：自顶向下效率低：保留现场，参数传递。时间：重复计算，空间：栈溢出 易证明止确性：数学归纳法2求最大公约数gcd(m,n)=gcd(n, m%n) m%n!=o;nelse;1)递推 #include<stdio.h>main()int m,n,t,mo,no; printf(hm

4、,nn);scanf(n%d%dn,&m,&n); mo=m;no=n;while(m%n!=o) t=m;m=n;n=t%n;printf(ngcd(%d,%d)=%dn",mo,no,n);函数:#include <stdio.h>int gcd(int a,int b) int t;while(a%b!=o) t=a；a=b;b=t%n;return(n);void main() int m,n ;printf(ninput two integer:11);scanf(h%d,%dn,&m, &n);printf(ngcd(%d,%d

5、) = %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(ninput two integer:11);scanf(h%d,%dh,&m, &n); printf(hgcd(%d,%d) = %d n'm,n,gcd(m,n);3. hanoi塔问题(地球末日问题)1844亿亿次，每次0.01秒，计60亿年p: hanoi塔问题a:

6、hanoi(n, a, b, c)=厂hanoi(n-1, a, c, b)move(n, a, b)if(n>l)s hanoi(n-1, c, b, a)乂 move(n, a, b)if(n=l)f: main()hanoi(n,a,c,b)move(n, a, b)#include<stdio.h>void hanoi(int n,char a,char c,char b);void move(int n, char a, char b);main()int n;printf(ninput the number of disks:”)；scanf(n%dn,&

7、n);printf("steps of moving %d disks from a to b by means of c:nn,n);hanoi(n, a,e,c);void hanoi(int n,char a,char c,char b)if(n=l) move(n,a,b);else hanoi(n-1, a, c, b);move(n, a, b);hanoi(n-1, c, b, a);void move(int n, char a, char b)printf(nmove %d: form %c to %cn",n,a,b);一致性:函数先声明再使用两种声明方法np完全问题1. p多项式问题，如求ln以内素数o(n*sqrt(n)0易解2. np非多项式问题