浅析递归

1.递归的思想：

设计一个递归函数，明确这个递归函数的定义，在这个函数里面反复调用自己从而求出问题的解。递归很多时候用于求有多少种解法的题目：这时要分清有多少种情况，然后把每一种情况产生的解的个数相加。

2.例题分析

（1）放苹果：M个同样的苹果放N个同样的盘子，允许有盘子空着, 问有多少种放法。注意：5 1 1和1 5 1是同一种放法

     分析：分两种情况：a.至少有一个盘子为空，此时放法种数与减去这个空盘子的放法种数相同。b.所有盘子都不为空，此时可以从每个盘子里拿掉一个苹果而不影响放法种数。

显然m<n时，只能满足第一种情况.

     代码：

#include<stdio.h>

 

//m个苹果放n个盘子里的放法种数

int setApple(int m,int n)

{

         if(m<=1||n==1)

                   return 1;

         if(n==0)

                   return 0;

         if(n>m)//至少有一个盘子为空

                   return setApple(m,n-1);

         else//至少一个盘子为空 + 所有盘子都不为空

             return setApple(m,n-1)+setApple(m-n,n);

}

 

void main()

{

         printf("%d\n",setApple(7,3));

}

（2）红与黑：有一间房子铺有红色和黑色的砖块，人站在一个黑色砖块上面，且每次只能移动到黑色砖块，不能走走过的砖块。求他所能到达的黑色砖块的数目。如：

char house[9][6]={

{"......"},

{".@..##"},

{"..#.#."},

{".#.##."},

{"#...#."},

{"....#."},

{"....#."},

{"....#."},

{".....#"}

};

‘.’表示黑色砖块，’@’表示黑色砖块且人所在的当前位置，’#’表示红色砖块

分析：分四种情况，上、下、左、右。这四种情况下所能到达的数目和当前位置加起来就是总共能到达的数目.

代码:

#include<stdio.h>

 

char house[9][6]={

{"......"},

{".@..##"},

{"..#.#."},

{".#.##."},

{"#...#."},

{"....#."},

{"....#."},

{"....#."},

{".....#"}

};

int m=9;

int n=6;

 

//求初始位置在（i，j）时能到达的黑砖的个数

int move(int i,int j)

{

         if(house[i][j]=='@')

       house[i][j]='.';

         if(i<0 || j<0 || i>=m || j>=n || house[i][j]!='.')

                   return 0;

         else//到达过的做标记

                   house[i][j]='0';

         //每个点有四种走法

         return 1+move(i-1,j)+move(i+1,j)+move(i,j-1)+move(i,j+1);            

}

 

void main()

{

         printf("%d\n",move(1,1));

}

（3）计算3个A，2个B可以组成多少种排列的问题（如：AAABB, AABBA）是《组合数学》的研究领域。但有些情况下，也可以利用计算机计算速度快的特点通过巧妙的推理来解决问题。下列的程序计算了m个A，n个B可以组合成多少个不同排列的问题。请完善它。

int f(int m, int n)

{

    if(m==0 || n==0) return 1;

    return ____ f(m-1, n) + f(m, n-1)___________________;

}

    分析：首先明确这个函数的功能是：求m个A和n个B可以组成多少种排列。此时分两种情况：a.排列的第一个元素是A。b.排列的第一个元素是B。把这两种情况的排列种数加起来即可.

   （4）某布袋中有红球m个，白球n个，现在要从中取出x个求，红球数目多于白球的数目的概率是多少。下面的代码解决这个问题，其中y表示红球至少要出现的次数。

m , n, x, y为仅存线索

double f( int m, int n, int x,int y)

{

if(y>x) return 0;

if(y==0) return 1;

if(y>m) return 0;

if(x-n>y) return 1;

double p1=________________; f(m-1,n,x-1,y-1)

double p2=________________; f(m,n-1,x-1,y)

return (double)m/(m+n)*p1+(double)n/(m+n)*p2;

}

    分析：明确函数的定义：求m个红球、n个白球的布袋中取出x个球，红球数目大于白球的概率。注意到m/(m+n)表示取出的球是红球的概率，n/(m+n)表示取出的球是白球的概率。现在从布袋中取一个球出来，有两种情况：a.取出的是红球 b.取出的是白球.然后根据不同的情况判断m、n、x、y的变化。

（5）假设有m+n个人，其中，m个人手持面额为5角的硬币，n个人手持面额为1元的硬币，他们都要乘车买票，现假设售票员手中无零钞，票价为5角，下面这个函数就可以算出这m+n个人所有可能的买票情况（顺利完成购票过程的购票次序的种类数），请完善此函数

int f(int m, int n) 
{ 
        if(m < n) return 0; 
        if(n==0) return 1; 
        return ____ f(m-1 , n) + f( m-1 , n-1) ___; 
}

分析：这题跟上题有点相似，上题是模拟从布袋中取一个球出来，这个球可能是红球，也可能是白球。这里是模拟一个人上车，这个人可能是持5角的硬币，也可能是持1块的硬币。第一种情况下这个人直接上车，第二种情况下手持1块钱硬币的人要等有一个手持5角的人上车。

 

3.总结

  递归是很多算法的基础，递归的难点是构造递归函数和分清楚情况。在分情况时很多都是模拟现实中的情况，如上面的第1、4、5题。

4.递归函数设计

（1）整数划分

如，对于正整数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+1

总共有十一种划分，求一个数总共有多少种这样的划分。

 

代码：

/*

 * 整数划分

 * 划分出去一个整数， n==m 时，有两种情况：

 *

 * 划分出去的整数等于n+划分出去的整数小于n

 

 * n>m时：

 * 划分出去的数小于m+划分出去的数等于m

 *

 */

 

#include<stdio.h>

 

//正整数n最大加数n1不大于m的划分个数

int divide(int n,int m)

{

     if(n==1 || m==1)

              return 1;

     if(n<m)

              return divide(n,n);

     else if(n==m)

              //最大加数等于n+最大加数<n

              //比如n=6：最大加数是6的划分的划分个数+6不大于5的划分个数

              return 1+divide(n,m-1);

     else

              //最大加数小于m的个数+最大加数为m时的个数

              //如n=6，m=2：6不大于1的划分个数+4不大于2的划分个数

              //（处理m=2的那一行,其中这行减2之后就是4不大于2的划分个数）

              return divide(n,m-1)+divide(n-m,m);

}

（2）木棍问题

 一组等长的的木棍，随机的截断，使每一段不超过50个长度单位。然后又想把这些木棒恢复到截断前的状态，但忘记了初始时有多少根木棒以及木棒的初始长度。计算木棒初始时可能的最小长度。每一节木棒长度都用大于0 的整数表示。

代码：

/*

 * 木棒截断问题（递归）

 *

 * 题目：一组等长的的木棍，随机的截断，使每一段不超过50个长度单位。

 * 然后又想把这些木棒恢复到截断前的状态，但忘记了初始时有多少

 * 根木棒以及木棒的初始长度。计算木棒初始时可能的最小长度。每

 * 一节木棒长度都用大于0 的整数表示。

 *

 * 思路：假设这组木棒的总长度是M，截断后最大的长度为P，初始时可能

 *       的最小长度为L。则L>=P,且M整除L。所以可以从P开始搜索L的可能

 *       值。设计一个递归函数判断L是否可能是原始木棒的长度。

 */

 

#include<stdio.h>

 

#define MAX_NUM 50 //截断后木棒的节数

 

int a[MAX_NUM];    //存放截断后各节木棒的长度

int num;           //木棒的个数

int used[MAX_NUM]={0};//木棒是否被使用，即是否以被拼接

 

//初始化a数组和num

void init()

{

     int i;

     printf("输入截断后木棒节数：\n");

     scanf("%d",&num);

     printf("输入截断后各节木棒的长度：\n");

     for(i=0;i<num;i++)

         scanf("%d",&a[i]);

}

 

//对木棒长度从大到小冒泡排序

void sort()

{

     int i,j,temp;

     for(i=0;i<num;i++)

              for(j=0;j<num-1;j++){

                       if(a[j]<a[j+1]){

                                 temp=a[j];

                                 a[j]=a[j+1];

                                 a[j+1]=temp;

                       }

              }

}

 

//判断某个长度是否可能是原始木棒的长度

//stickNum是截断后木棒总节数，unuseStickNum是未被拼接的木棒节数

//left当前剩余可拼接的长度，len正在尝试的原始木棒长度

int can(int stickNum,int unuseStickNum,int left,int len)

{

     int i;

     if(left==0 && unuseStickNum==0)

              return 1;

     if(left==0)

              left=len;

    for(i=0;i<stickNum;i++){

              if(used[i])

                       continue;

              if(a[i]>left)

                       continue;

              used[i]=1;

              if(can(stickNum,unuseStickNum-1,left-a[i],len))

                       return 1;

              used[i]=0;

     }

     return 0;

}

 

//从最大的那节木棒开始寻找可能的长度

void search()

{

     int i;

     int sum=0;

     for(i=0;i<num;i++)

              sum+=a[i];

     for(i=a[0];i<=sum;i++){

              if(sum%i!=0)

                       continue;

              if(can(num,num,i,i)){

                       printf("%d\n",i);

                       break;

              }

     }

     if(i>sum)

              printf("error\n");

}

 

void main()

{

     init();

     sort();

     search();

}