递归算法的学习

 能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题， 然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法， 分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。

示例：小猴吃枣

   小猴第一天摘下若干枣子，当即吃掉了一半，不过瘾又多吃了一个；第二天吃了剩下的一半又多吃了一个；

以后每一天都吃了前一天剩下的一半多一个。到第十天小猴再想吃时，见到只剩下一只枣子了。问第一天这堆枣子有多少？

   从上题中我们可看到一个令人欣喜的规律，第十天为1，第九到第一天中后一天与1的和的两倍与前一天相等。

下面就对这一规律做了描述：(完整的程序请下载）

public int taozi(int x){

  if(x>=10) {

   return 1;

  }

  else{

    return 2*(taozi(x+1)+1);

  }

}

我们定义taozi()函数的时候通过taozi()自身来进行了定义，这就是递归。 递归是个特殊的循环，是一个有着非常美妙的循环规则的循环。 上题中我们只要将taozi(1)，即第一天打印出来，一切OK。而这中间究竟是怎么工作的，我们可以不管。

【问题】 组合问题

问题描述：找出从自然数1、2、……、n中任取r个数的所有组合。

例如 n=5，r=3的所有组合为： 

（1）5、4、3   （2）5、4、2    （3）5、4、1

(4）5、3、2    （5）5、3、1    （6）5、2、1

(7）4、3、2    （8）4、3、1    （9）4、2、1

(10）3、2、1

分析所列的10个组合，可以采用这样的递归思想来考虑求组合函数的算法。 设函数为public void comb(int m,int k)为找出从自然数1、2、……、m中任取k个数的所有组合。 当组合的第一个数字选定时，其后的数字是从余下的m-1个数中取k-1数的组合。

这就将求m 个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。

  设函数引入工作数组a[]存放求出的组合的数字，约定函数将确定的k个数字组合的第一个数字放在a[k]中， 当一个组合求出后，才将a[]中的一个组合输出。

   第一个数可以是m、m-1、……、k，函数将确定组合的第一个数字放入数组后， 有两种可能的选择，因还未确定组合的其余元素，继续递归去确定；或因已确定了组合的全部元素， 输出这个组合。细节见以下程序:

public class CombTest{ static int   a[]=new int[100];  static void  comb(int m,int k) {    int i,j;    for (i=m;i>=k;i--)  {     a[k]=i;       if (k>1)          comb(i-1,k-1);       else {           for (j=a[0];j>0;j--)             System.out.printf("%4d",a[j]);             System.out.println();       }    } }  public static void main(String args[]) {      a[0]=3;      comb(5,3);      // a[0]=4;     // comb(10,4); } } 运行： C:\java>java    CombTest    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