java递归算法入门小结（一）

妖狐艹你老母 2022-08-18 03:12 2阅读 0赞

> > > > > > >     \*\*  java递归问题小结\*\*

对于一个复杂的问题，把原问题分解为若干个相对简单类同的子问题，继续下去直到子问题简单到能够直接求解，也就是说到了递推的出口，这样原问题就有递推得解。  
      在做递归算法的时候，一定要把握住出口，也就是做递归算法必须要有一个明确的递归结束条件。这一点是非常重要的。其实这个出口是非常好理解的，就是一个条件，当满足了这个条件的时候我们就不再递归了。  
关键要抓住的是：  
（1）递归出口  
（2）逐步向出口逼近  
  
下面举一些常用的例子  
1 如 1+2+3+4+5+.......100  
  
     /\*\*  
     \* 下面的算法是算1+2+3+……的  
     \* @param num  
     \* @return  
     \*/  
    public static long sum(int num) \{   
        if (num > 0) \{   
            return num + sum(num - 1); // 调用递归方法  
        \} else \{   
            return 0; // 当num=0时，循环结束  
        \}  
    \}  
2     
     /\*\*  
     \* 下面的算法是算1+1/2+1/3+……；  
     \* @param n  
     \* @return  
     \*/  
    public static double add(int n)\{   
        if(n==1)\{   
            return 1.0/1;  
        \}  
        else\{   
            return 1.0/n + add(n-1);  
        \}  
    \}  
3      
     /\*\*  
     \* 下面的算法是算1 *\*2\**3\*.......  
     \* @param input  
     \* @return  
     \*/  
    public static double multiplication(long input)\{   
        if(input==1)\{   
            return 1;  
        \}else\{   
            return input\*multiplication(input-1);  
        \}  
    \}  
  
4 Fibonacci数列：1，1，2，3，5，8，13……  
  要求：找出数列中指定index位置的数值  
  
   private static long fab(int index) \{    
        if (index == 1 || index == 2) \{    
            return 1;    
        \} else \{    
            return fab(index - 1) + fab(index - 2);    
        \}    
    \}