有关递归的若干例子收集
今天在网上看到一个递归的总结，感觉不错，拿下来与大家分享！
//递归例子
//1。求1+2+。。+100的和
int sum(int n){
??? if(n==1)return 1;
??? else returnn+sum(n-1);
}
#include <stdio.h>
// 2.求m*n的乘积
int multiply(int m,int n){
???if(n==1)return m;
??? else returnm+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(n<length){
?????????reverse(p,length,n+1);
?????????printf("%c",p[n]);
????}
}
//5.求数组中的最大值
int max(int *a,int n){
??? if(n==1)return a[0];
??? else {
????????if(a[n-1]>max(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<m) return gcd(m,n);
??? if(m==0)return n;
??? else returngcd(m,n%m);
}
//10.折半查找的递退公式
int bsearch(int i[],int x,int n){
??? intlow=0,high=n-1;
???
???while(low<=high){
???????int mid=low+high/1;
???????if(x==i[mid]) return mid;
???????else if(x<i[mid]) high=mid-1;
???????elselow=mid+1;????????????
??? }
??? return-1;
}
//11.求组合个数
//组合递推公式为comn(m,n)=comn(m-1,n-1)+comn(m-1,n);
long comn(int m,int n){
????if(n==0||m==n)return 1;
????else return comn(m-1,n-1)+comn(m-1,n);
????}
//12。背包问题
int Knap(int s,int w[],int n){
??? if(s==0)return 1;
???if(s<0)? return 0;
???if(s>0&&n<1)return 0;
???if(s>0&&n>=1){
??????if(Knap(s,w,n-1)==1) return 1;
??????else? if (Knap(s-w[n-1],w,n-1)==1) return1;??????????
??? }else return0;
???
}
13.组合问题
#include <stdio.h>
#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 <stdio.h>
?int n = 0;?
?void swap(int *a, int *b)
? {? intm;??????
????m =*a;???????
??? *a =*b;??????
??? *b =m;
? }
?? void perm(int list[], int k,int m)
??{????????inti;?????
?????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种。下面介绍一种通过递归方法得到一个正整数的划分数。
???
??? 递归函数的声明为 intsplit(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< n
???这是最一般的情况，在划分的大多数时都是这种情况。
??? 从上例可以看出，设m =4，那split(6, 4)的值是最大加数小于4划分数和整数2的划分数的和。
??? 因此，split(n,m)可表示为split(n, m - 1) + split(n - m, m)
???
???根据以上描述，可得源程序如下：
??
?? #include<stdio.h>
?? int split(int n, int m)
?? {
???? if(n < 1 || m< 1) return 0;
? ? ? if(n == 1|| m == 1) return 1;
? ? ? if(n< m) return split(n, n);
???? if(n == m) return (split(n, m- 1) + 1);
???? if(n > m)return (split(n, m - 1) + split((n - m), m));
? }
int main()
{
?? ?printf("12的划分数: %d", split(12, 12));
??? return0;
}
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){};
}
