快捷導(dǎo)航

java編程之遞歸算法總結(jié)

更新時(shí)間：2017年11月07日 17:10:25 作者：toMatser

這篇文章主要介紹了java編程之遞歸算法總結(jié)，具有一定參考價(jià)值，需要的朋友可以了解下。

1.何為遞歸

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

2.遞歸算法設(shè)計(jì)的基本思想是：

對(duì)于一個(gè)復(fù)雜的問(wèn)題，把原問(wèn)題分解為若干個(gè)相對(duì)簡(jiǎn)單類(lèi)同的子問(wèn)題，繼續(xù)下去直到子問(wèn)題簡(jiǎn)單到能夠直接求解，也就是說(shuō)到了遞推的出口，這樣原問(wèn)題就有遞推得解。

關(guān)鍵要抓住的是：

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

3.常見(jiàn)遞歸算法

（1）最常見(jiàn)的就是階乘，比如求5的階乘，數(shù)學(xué)公式就是：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("執(zhí)行第" + 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個(gè)數(shù)

  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);
  }

用遞歸方式實(shí)現(xiàn) 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打印九九除法表代碼分析

遞歸的效率問(wèn)題及遞歸與循環(huán)比較

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

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

2.用循環(huán)效率會(huì)比遞歸效率高嗎？

遞歸與循環(huán)是兩種不同的解決問(wèn)題的典型思路。當(dāng)然也并不是說(shuō)循環(huán)效率就一定比遞歸高，遞歸和循環(huán)是兩碼事，遞歸帶有棧操作，循環(huán)則不一定，兩個(gè)概念不是一個(gè)層次，不同場(chǎng)景做不同的嘗試。

2.1遞歸算法：

優(yōu)點(diǎn)：代碼簡(jiǎn)潔、清晰，并且容易驗(yàn)證正確性。（如果你真的理解了算法的話，否則你更暈）

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

2.2循環(huán)算法：

優(yōu)點(diǎn)：速度快，結(jié)構(gòu)簡(jiǎn)單。

缺點(diǎn)：并不能解決所有的問(wèn)題。有的問(wèn)題適合使用遞歸而不是循環(huán)。如果使用循環(huán)并不困難的話，最好使用循環(huán)。

2.3遞歸算法和循環(huán)算法總結(jié)：

1.一般遞歸調(diào)用可以處理的算法，也通過(guò)循環(huán)去解決常需要額外的低效處理。

2.現(xiàn)在的編譯器在優(yōu)化后，對(duì)于多次調(diào)用的函數(shù)處理會(huì)有非常好的效率優(yōu)化，效率未必低于循環(huán)。

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

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

首先，看一下系統(tǒng)棧和用戶棧的用途。

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

3.2用戶棧是用戶進(jìn)程空間中的一塊區(qū)域，用于保存用戶進(jìn)程的子程序間相互調(diào)用的參數(shù)、返回值、返回點(diǎn)以及子程序(函數(shù))的局部變量。

我們編寫(xiě)的遞歸程序?qū)儆谟脩舫绦?，因此使用的是用戶?！?/p>

總結(jié)

以上就是本文關(guān)于java編程之遞歸算法總結(jié)的全部?jī)?nèi)容，希望對(duì)大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站：java實(shí)現(xiàn)的各種排序算法代碼示例、Java算法之堆排序代碼示例、Java 蒙特卡洛算法求圓周率近似值實(shí)例詳解等，有什么問(wèn)題可以隨時(shí)留言，小編會(huì)及時(shí)回復(fù)大家的。感謝朋友們對(duì)本站的支持！

您可能感興趣的文章: