前言

最近在看書(shū)的時(shí)候看到這一內(nèi)容，感覺(jué)還是蠻有收獲的。迭代使用的是循環(huán)（for，while，do...wile）或者迭代器，當(dāng)循環(huán)條件不滿足時(shí)退出。而遞歸，一般是函數(shù)遞歸，可以是自身調(diào)用自身，也可以是非直接調(diào)用，即方法A調(diào)用方法B,而方法B反過(guò)來(lái)調(diào)用方法A，遞歸退出的條件為if，else語(yǔ)句，當(dāng)條件符合基的時(shí)候退出。

上面是迭代和遞歸的語(yǔ)法特性，他們?cè)贘ava中有什么不同呢？下面通過(guò)這篇文章來(lái)詳細(xì)了解了解。

一、遞歸

提到迭代，不得不提一個(gè)數(shù)學(xué)表達(dá)式： n!=n*(n-1)*(n-2)*...*1

有很多方法來(lái)計(jì)算階乘。有一定數(shù)學(xué)基礎(chǔ)的人都知道n!=n*(n-1)!因此，代碼的實(shí)現(xiàn)可以直接寫(xiě)成：

代碼一

int factorial (int n) {
 if (n == 1) {
  return 1;
 } else {
  return n*factorial(n-1);
 }
} 

在執(zhí)行以上代碼的時(shí)候，其實(shí)機(jī)器是要執(zhí)行一系列乘法的： factorial(n) → factorial(n-1) → factorial(n-2) → … → factorial(1) 。所以，需要不斷的跟蹤（跟蹤上次計(jì)算的結(jié)果）并調(diào)用乘法進(jìn)行計(jì)算（構(gòu)建一個(gè)乘法鏈）。這類不斷調(diào)用自身的運(yùn)算形式稱之為遞歸。遞歸可以進(jìn)一步的分為線性遞歸和數(shù)形遞歸。信息量隨著算法的輸入呈線性增長(zhǎng)的遞歸稱之為線性遞歸。計(jì)算n!（階乘）就是線性遞歸。因?yàn)殡S著N的增大，計(jì)算所需的時(shí)間呈線性增長(zhǎng)。另外一種信息量隨著輸入的增長(zhǎng)而進(jìn)行指數(shù)增長(zhǎng)的稱之為樹(shù)形遞歸。

二、迭代

另外一種計(jì)算n!的方式是：先計(jì)算1乘以2，然后用其結(jié)果乘以3，再用的到的結(jié)果乘以4….一直乘到N。在程序?qū)崿F(xiàn)時(shí)，可以定義一個(gè)計(jì)數(shù)器，每進(jìn)行一次乘法，計(jì)數(shù)器都自增一次，直到計(jì)數(shù)器的值等于N截至。代碼如下：

代碼二

int factorial (int n) {
 int product = 1;
 for(int i=2; i<n; i++) {
  product *= i;
 }
 return product;
}

和代碼一相比，代碼二沒(méi)有構(gòu)建一個(gè)乘法鏈。在進(jìn)行每一步計(jì)算時(shí)，只需要知道當(dāng)前結(jié)果（product）和i的值就可以了。這種計(jì)算形式稱之為迭代。迭代有這樣幾個(gè)條件：1、有一個(gè)有初始值的變量。2、一個(gè)說(shuō)明變量值如何更新的規(guī)則。3、一個(gè)結(jié)束條件。（循環(huán)三要素：循環(huán)變量、循環(huán)體和循環(huán)終止條件）。和遞歸一樣。時(shí)間要求隨著輸入的增長(zhǎng)呈線性的可以叫做線性迭代。

三、迭代 VS 遞歸

比較了兩個(gè)程序，我們可以發(fā)現(xiàn)，他們看起來(lái)幾乎相同，特別是其數(shù)學(xué)函數(shù)方面。在計(jì)算n!的時(shí)候，他們的計(jì)算步數(shù)都是和n的值成正比的。但是，如果我們站在程序的角度，考慮他們是如何運(yùn)行的話，那么這兩個(gè)算法就有很大不同了。

（注：原文中關(guān)于其區(qū)別寫(xiě)的有點(diǎn)扯，這里就不翻譯了，下面是筆者自己總結(jié)內(nèi)容。）

首先分析遞歸，其實(shí)遞歸最大的有點(diǎn)就是把一個(gè)復(fù)雜的算法分解成若干相同的可重復(fù)的步驟。所以，使用遞歸實(shí)現(xiàn)一個(gè)計(jì)算邏輯往往只需要很短的代碼就能解決，并且這樣的代碼也比較容易理解。但是，遞歸就意味著大量的函數(shù)調(diào)用。函數(shù)調(diào)用的局部狀態(tài)之所以用棧來(lái)記錄的。所以，這樣就可能浪費(fèi)大量的空間，如果遞歸太深的話還有可能導(dǎo)致堆棧溢出。

接下來(lái)分析迭代。其實(shí)，遞歸都可以用迭代來(lái)代替。但是相對(duì)于遞歸的簡(jiǎn)單易懂，迭代就比較生硬難懂了。尤其是遇到一個(gè)比較復(fù)雜的場(chǎng)景的時(shí)候。但是，代碼的難以理解帶來(lái)的有點(diǎn)也比較明顯。迭代的效率比遞歸要高，并且在空間消耗上也比較小。

      遞歸中一定有迭代，但是迭代中不一定有遞歸，大部分可以相互轉(zhuǎn)換。

      能用迭代的不要用遞歸，遞歸調(diào)用函數(shù)不僅浪費(fèi)空間，如果遞歸太深的話還容易造成堆棧的溢出。

四、數(shù)形遞歸

前面介紹過(guò)，樹(shù)遞歸隨輸入的增長(zhǎng)的信息量呈指數(shù)級(jí)增長(zhǎng)。比較典型的就是斐波那契數(shù)列：

用文字描述就是斐波那契數(shù)列中前兩個(gè)數(shù)字的和等于第三個(gè)數(shù)字：0,1,1,2,3,5,8,13,21……

遞歸實(shí)現(xiàn)代碼如下：

int fib (int n) {
 if (n == 0) {
  return 0;
 } else if (n == 1) {
  return 1;
 } else {
  return fib(n-1) + fib(n-2);
 }
}

計(jì)算過(guò)程中，為了計(jì)算fib(5) ，程序要先計(jì)算fib(4) 和 fib(3) ，要想計(jì)算fib(4) ，程序同樣需要先計(jì)算 fib(3) 和 fib(2) 。在這個(gè)過(guò)程中計(jì)算了兩次fib(3)。

從上面分析的計(jì)算過(guò)程可以得出一個(gè)結(jié)論：使用遞歸實(shí)現(xiàn)斐波那契數(shù)列存在冗余計(jì)算。

就像上面提到的，可以用遞歸的算法一般都能用迭代實(shí)現(xiàn)，斐波那契數(shù)列的計(jì)算也一樣。

int fib (int n) {
 int fib = 0;
 int a = 1;
 for(int i=0; i<n; i++) {
  int temp = fib;
  fib = fib + a;
  a = temp;
 }
 return fib;
}

雖然使用遞歸的方式會(huì)有冗余計(jì)算，可以用迭代來(lái)代替。但是這并不表明遞歸可以完全被取代。因?yàn)檫f歸有更好的可讀性。

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家學(xué)習(xí)或者使用Java能有所幫助，如果有疑問(wèn)大家可以留言交流。

最新評(píng)論