Go语言视频零基础入门到精通

javalearner

递归是设计和描述算法的一种有力的工具，它在复杂算法的描述中被经常采用。
   
    能采用递归描述的算法通常有这样的特征：为求解规模为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。而这中间究竟是怎么工作的，我们可以不管。
  【问题】 编写计算斐波那契（Fibonacci）数列的第n项函数fib（n）。
斐波那契数列为：0、1、1、2、3、……，即：
   fib(0)=0;
   fib(1)=1;
   fib(n)=fib(n-1)+fib(n-2) （当n>1时）。
写成递归函数有：
  public int fib(int n){
    if (n==0) return 0;
    if (n==1) return 1;
    if (n>1) return fib(n-1)+fib(n-2);
}    递归算法的执行过程分递推和回归两个阶段。

在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。例如上例中，求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。 也就是说，为计算fib(n)，必须先计算 fib(n-1)和fib(n-2)，而计算fib(n-1)和fib(n-2)，又必须先计算fib(n-3)和fib(n-4)。依次类推，直至计算 fib(1)和fib(0)，分别能立即得到结果1和0。 在递推阶段，必须要有终止递归的情况。例如在函数fib中，当n为1和0的情况。

在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解，例如得到fib(1)和fib(0)后，
返回得到fib(2)的结果，……，在得到了fib(n-1)和fib(n-2)的结果后，返回得到fib(n)的结果。

   在编写递归函数时要注意，函数中的局部变量和参数只局限于当前调用层，当递推进入“简单问题”层时， 原来层次上的参数和局部变量便被隐蔽起来。在一系列 “简单问题”层，它们各有自己的参数和局部变量。由于递归引起一系列的函数调用，并且可能会有一系列的重复计算，递归算法的执行效率相对较低。 当某个递归算法能较方便地转换成递推算法时，通常按递推算法编写程序。
    例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法（用循环），即从斐波那契数列的前两项出发，
逐次由前两项计算出下一项，直至计算出要求的第n项。 【问题】 组合问题
问题描述：找出从自然数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，函数将确定组合的第一个数字放入数组后， 有两种可能的选择，因还未确定组合的其余元素，继续递归去确定；或因已确定了组合的全部元素， 输出这个组合。细节见以下程序:

1. public class CombTest{
   
2. static int   a[]=new int[100];
   
3. static void  comb(int m,int k) {
   
4.    int i,j;
   
5.    for (i=m;i>=k;i--)  {
   
6.      a[k]=i;
   
7.       if (k>1)
   
8.          comb(i-1,k-1);
   
9.       else {
   
10.            for (j=a[0];j>0;j--)
    
11.             System.out.printf("%4d",a[j]);
    
12.             System.out.println();
    
13.       }
    
14.    }
    
15. }
    
16. public static void main(String args[]) {
    
17.       a[0]=3;
    
18.       comb(5,3);
    
19.      // a[0]=4;
    
20.      // comb(10,4);
    
21. }
    
22. }
    
24. 运行：
25. C:java>java    CombTest
26.    5   4   3
27.    5   4   2
28.    5   4   1
29.    5   3   2
30.    5   3   1
31.    5   2   1
32.    4   3   2
33.    4   3   1
34.    4   2   1
35.    3   2   1

复制代码

  
  
   
   

     
   

     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/11/26/000602468.zip