有关递归的若干例子收集

今天在网上看到一个递归的总结，感觉不错，拿下来与大家分享！

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

// 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(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 return gcd(m,n%m);
}
//10.折半查找的递退公式
int bsearch(int i[],int x,int n){
      int low=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;
              else low=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) return 1;                   
      }else return 0;
     
}

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)
  {  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 < 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));
      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){};
}