递归例子

//递归例子
//1。求1+2+。。+100的和
int sum(int n){
if(n==1) return 1;
else return n+sum(n-1);
}
#include

// 2.求m*n的乘积
int multiply(int m,int n){
if(n==1)return m;
else return m+multiply(m,n-1);
}
//3.求阶乘
long fac(int n){
if(n==1)return 1;
else return n*fac(n-1);
}
//4.求字符数组的转置
void reverse(char *p,int length,int n){
if(nmax(a,n-1)) return a[n-1];
else return max(a,n-1);
}
}
//6.打印$
//4444
//333
//22
//1
void printNumber(int n){
if(n>=1){
for(int i=1;i<=n;i++) printf("%d",n); printf("\n"); printNumber(n-1); } } //6.打印$ //1 //22 //333 //4444 void printNumber2(int n){ if(n>0) printNumber(n-1);
for(int i=1;i<=n;i++) printf("%d",n); printf("\n"); } //7.计算费氏数列的变种 long clib(int n){ if(n==0||n==1) return n; else return 4*clib(n-2)+5*clib(n-1); } //8.计算递推公式 long F(int a,int n){ if(n==0) return 1; else return a*F(a,n/2); } //9最大公约数公式 int gcd(int n,int m){ if(n<=high){ int mid=low+high/1; if(x==i[mid]) return mid; else if(x0,n<1; s="="0，则有解。">0,然后再放置任意一件物品，s<0；无解 knap="Knap(s,w,n-1);所选物品不包括w[n-1]时" knap="knam[s-w[n-1],w,n-1]所选物品包括w[n-1]时" s="="0)">0&&n<1)>0&&n>=1){
if(Knap(s,w,n-1)==1) return 1;
else if (Knap(s-w[n-1],w,n-1)==1) return 1;
}else return 0;
13.组合问题
程序目的：打印从1,2,3..n个数中任选k个数的所有组合
例如从5个数中任取3个的所有组合，可得
5 4 3
5 4 2
5 4 1
5 3 2
5 3 1
5 2 1
4 3 2
4 3 1
4 2 1
3 2 1
第一个数从5到3
第二个数从4到2
第三个数从3到1
*/
#include
#define maxN 100
int a[maxN];
int size;
long sum=0;
void comn(int m,int k){
for(int i=m;i>=k;i--){ //第一个数从n,n-1到k
a[k]=i;
if(k>1)comn(i-1,k-1);//下一层递归比上层递归m小1；
else { //找到一组解，打印
++sum;
for(int j=size;j>0;j--)
printf("%d",a[j]);
printf("\n");
}
}
}main(){
size=3;
comn(8,5);
printf("共有%d组解",sum);
while(1){}

}
14。排列问题，求n!的所有排列问题#include
int n = 0;
void swap(int *a, int *b)
{ int m;
m = *a;
*a = *b;
*b = m;
}
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"); ++n; } else { for(i=k; i <= m; i++) { swap(&list[k], &list[i]); perm(list, k + 1, m); swap(&list[k], &list[i]); } } } int main() { int list[] = {1, 2, 3}; perm(list, 0, 2); printf("total:%d\n", n); for(int i = 0; i <= 2; i++) printf("%d ", list[i]); while(1){} return 0; } 15.整数划分问题

整数划分问题是将一个正整数n拆成一组数连加并等于n的形式，且这组数中的最大加数不大于n。
如6的整数划分为

6
5 + 1
4 + 2, 4 + 1 + 1
3 + 3, 3 + 2 + 1, 3 + 1 + 1 + 1
2 + 2 + 2, 2 + 2 + 1 + 1, 2 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1

共11种。下面介绍一种通过递归方法得到一个正整数的划分数。

递归函数的声明为 int split(int n, int m);其中n为要划分的正整数，m是划分中的最大加数(当m > n时，最大加数为n)，
1 当n = 1或m = 1时，split的值为1，可根据上例看出，只有一个划分1 或 1 + 1 + 1 + 1 + 1 + 1
可用程序表示为if(n == 1 || m == 1) return 1;

2 下面看一看m 和 n的关系。它们有三种关系
(1) m > n
在整数划分中实际上最大加数不能大于n，因此在这种情况可以等价为split(n, n);
可用程序表示为if(m > n) return split(n, n);
(2) m = n
这种情况可用递归表示为split(n, m - 1) + 1，从以上例子中可以看出，就是最大加
数为6和小于6的划分之和
用程序表示为if(m == n) return (split(n, m - 1) + 1);
(3) m < m =" 4，那split(6,">

int split(int n, int m)
{
if(n < n ="="" m ="="" n ="=""> m) return (split(n, m - 1) + split((n - m), m));
}

int main()
{
printf("12的划分数: %d", split(12, 12));
return 0;
}

main(){
char a[]={'a','b','c','d'};
int b[]={1,20,100,-5,7};
int i[]={1,2,3,4,5,6,7,8};
//reverse(a,4,0);
//printNumber2(4);

printf("%d\n",bsearch(i,4,8));
while(1){};
}