4.3 复杂递归.doc

复杂递归： 将正整数n逆序输出 reverse(n)=n%10;reverse(n/10) , n=10 n , else 1)递推 #includestdio.h void reverse(int n); main() { int m; printf(m=); scanf(%d,m); reverse(m); } void reverse(int n) { while(n=10) { printf(%d,n%10); n=n/10; } printf(%d,n); } 2)递归 main() { int m; printf(“m=”); scanf(“%d”,m); reverse(m); } void reverse(int n) { if(n=9) printf(“%d”,n); else{ printf(“%d”,n%10); reverse(n/10); } } 全排列问题 perm(list[k..m])= i:k-m, list[k]-list[i]; perm(list[k+1..m]); list[k]-list[i] , km list[0..m] , k==m #includestdio.h void perm(int list[],int k,int m); void swap(int *x,int *y); int count; //全局变量 main() { int list[]={1,2,3,4,5}; perm(list, 0, 4); printf(count=%d\n,count); } void perm(int list[],int k,int m) { int i; if(k==m) { for(i=0;i=m;i++) printf(%d, list[i]); printf(\n); count++; } else for(i=k;i=m;i++) { swap(list[k],list[i]); perm(list,k+1,m); swap(list[k],list[i]); } } inline void swap(int *x,int *y) { int t; t=*x; *x=*y; *y=t; } 分解： main(),void perm(int list[],int k,int m), void swap(int *x,int *y) 全局变量count，统计排列数 性质： 一致性：传址要保证实参与形参的数据类型（即地址或指针）一致性