java編程之遞歸算法總結

1.何為遞歸

個人理解就是自己調用自己，直到滿足一個條件結束自己調用自己的過程，這個就是遞歸。舉一個通俗的點的例子：
假設你在一個電影院，你想知道自己坐在哪一排，但是前面人很多，你懶得去數了，于是你問前一排的人「你坐在哪一排？」，這樣前面的人 (代號 A) 回答你以后，你就知道自己在哪一排了——只要把 A 的答案加一，就是自己所在的排了，不料 A 比你還懶，他也不想數，于是他也問他前面的人 B「你坐在哪一排？」，這樣 A 可以用和你一模一樣的步驟知道自己所在的排。然后 B 也如法炮制，直到他們這一串人問到了最前面的一排（或者說問到了知道自己是哪一排的人，預示著調用結束），第一排的人告訴問問題的人「我在第一排」，最后大家就都知道自己在哪一排了

2.遞歸算法設計的基本思想是：

對于一個復雜的問題，把原問題分解為若干個相對簡單類同的子問題，繼續下去直到子問題簡單到能夠直接求解，也就是說到了遞推的出口，這樣原問題就有遞推得解。

關鍵要抓住的是：

（1）遞歸出口
（2）地推逐步向出口逼近

3.常見遞歸算法

（1）最常見的就是階乘，比如求5的階乘，數學公式就是：5*4*3*2*1，代碼：

package suanfa;
/**
 * Created by tl on 2016/4/10.
 */
public class Digui {
  public static int digui(int n){
    if(n==1||n==0){
      return n;
    }else{
      System.out.println("執行第" + n + "次");
      return n*digui(n-1);
    }
  }
public static void main (String[] args){
  System.out.print(digui(5));
}

（2）求1+2+3+4+5+6+7……+1000的和

  static int count(int n){
    if(n>0){
      return n+count(n-1);
    }else{
      return 0;
    }
  }
  public static void main(String args[])
  {
    int sum=count(1000);
    System.out.println(sum);
  }
}

（3）1,1,2,3,5,8,13,21,34...，求用遞歸算第30個數

  static int count(int n){
    if(n==1||n==2) {
      return 1;
    }
     return count(n-1)+count(n-2);
  }
  public static void main(String args[])
  {
    int sum=count(30);
    System.out.println(sum);
  }

用遞歸方式實現 99乘法表

代碼如下：

package test.ms;
public class MultiTable {
 public static void main(String args[]) { 
  m(9); 
 } 
 /** 
  * 打印出九九乘法表 
  * @param i 
  */
 public static void m(int i) { 
  if (i == 1) { 
   System.out.println("1*1=1 "); 
  } else { 
   m(i - 1); 
   for (int j = 1; j <= i; j++) { 
    System.out.print(j + "*" + i + "=" + j * i + " "); 
   } 
   System.out.println(); 
  } 
 } 
}

用Java打印九九除法表代碼分析

遞歸的效率問題及遞歸與循環比較

1.所謂的遞歸慢到底是什么原因呢？

大家都知道遞歸的實現是通過調用函數本身，函數調用的時候，每次調用時要做地址保存，參數傳遞等，這是通過一個遞歸工作棧實現的。具體是每次調用函數本身要保存的內容包括：局部變量、形參、調用函數地址、返回值。那么，如果遞歸調用N次，就要分配N*局部變量、N*形參、N*調用函數地址、N*返回值。這勢必是影響效率的。

2.用循環效率會比遞歸效率高嗎？

遞歸與循環是兩種不同的解決問題的典型思路。當然也并不是說循環效率就一定比遞歸高，遞歸和循環是兩碼事，遞歸帶有棧操作，循環則不一定，兩個概念不是一個層次，不同場景做不同的嘗試。

2.1遞歸算法：

優點：代碼簡潔、清晰，并且容易驗證正確性。（如果你真的理解了算法的話，否則你更暈）

缺點：它的運行需要較多次數的函數調用，如果調用層數比較深，需要增加額外的堆棧處理（還有可能出現堆棧溢出的情況），比如參數傳遞需要壓棧等操作，會對執行效率有一定影響。但是，對于某些問題，如果不使用遞歸，那將是極端難看的代碼。

2.2循環算法：

優點：速度快，結構簡單。

缺點：并不能解決所有的問題。有的問題適合使用遞歸而不是循環。如果使用循環并不困難的話，最好使用循環。

2.3遞歸算法和循環算法總結：

1.一般遞歸調用可以處理的算法，也通過循環去解決常需要額外的低效處理。

2.現在的編譯器在優化后，對于多次調用的函數處理會有非常好的效率優化，效率未必低于循環。

3.遞歸和循環兩者完全可以互換。如果用到遞歸的地方可以很方便使用循環替換，而不影響程序的閱讀，那么替換成遞歸往往是好的。（例如：求階乘的遞歸實現與循環實現。）

3.那么遞歸使用的棧是什么樣的一個棧呢？

首先，看一下系統棧和用戶棧的用途。

3.1系統棧（也叫核心棧、內核棧）是內存中屬于操作系統空間的一塊區域，其主要用途為：(1)保存中斷現場，對于嵌套中斷，被中斷程序的現場信息依次壓入系統棧，中斷返回時逆序彈出；(2)保存操作系統子程序間相互調用的參數、返回值、返回點以及子程序(函數)的局部變量。

3.2用戶棧是用戶進程空間中的一塊區域，用于保存用戶進程的子程序間相互調用的參數、返回值、返回點以及子程序(函數)的局部變量。

我們編寫的遞歸程序屬于用戶程序，因此使用的是用戶棧。

總結

以上就是本文關于java編程之遞歸算法總結的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續參閱本站：java實現的各種排序算法代碼示例、Java算法之堆排序代碼示例、Java 蒙特卡洛算法求圓周率近似值實例詳解等，有什么問題可以隨時留言，小編會及時回復大家的。感謝朋友們對本站的支持！