- 相關(guān)推薦
詳解Java中的迭代和遞歸
本文是百分網(wǎng)小編搜索整理的關(guān)于Java中的迭代和遞歸，文章顯示分別介紹了Java中的迭代和遞歸，而后又介紹了迭代和遞歸的區別以及數形遞歸的相關(guān)內容，感興趣的小伙伴們可以參考一下!想了解更多相關(guān)信息請持續關(guān)注我們應屆畢業(yè)生考試網(wǎng)!
前言
迭代使用的是循環(huán)（for，while，do...wile）或者迭代器，當循環(huán)條件不滿(mǎn)足時(shí)退出。而遞歸，一般是函數遞歸，可以是自身調用自身，也可以是非直接調用，即方法A調用方法B,而方法B反過(guò)來(lái)調用方法A，遞歸退出的條件為if，else語(yǔ)句，當條件符合基的時(shí)候退出。
上面是迭代和遞歸的語(yǔ)法特性，他們在Java中有什么不同呢？
一、遞歸
提到迭代，不得不提一個(gè)數學(xué)表達式： n!=n*(n-1)*(n-2)*...*1
有很多方法來(lái)計算階乘。有一定數學(xué)基礎的人都知道n!=n*(n-1)!因此，代碼的實(shí)現可以直接寫(xiě)成：
代碼一
int factorial (int n) {
if (n == 1) {
return 1;
} else {
return n*factorial(n-1);
}
}
在執行以上代碼的時(shí)候，其實(shí)機器是要執行一系列乘法的： factorial(n) → factorial(n-1) → factorial(n-2) → … → factorial(1) 。所以，需要不斷的跟蹤（跟蹤上次計算的結果）并調用乘法進(jìn)行計算（構建一個(gè)乘法鏈）。這類(lèi)不斷調用自身的運算形式稱(chēng)之為遞歸。遞歸可以進(jìn)一步的分為線(xiàn)性遞歸和數形遞歸。信息量隨著(zhù)算法的輸入呈線(xiàn)性增長(cháng)的遞歸稱(chēng)之為線(xiàn)性遞歸。計算n!（階乘）就是線(xiàn)性遞歸。因為隨著(zhù)N的增大，計算所需的時(shí)間呈線(xiàn)性增長(cháng)。另外一種信息量隨著(zhù)輸入的增長(cháng)而進(jìn)行指數增長(cháng)的稱(chēng)之為樹(shù)形遞歸。
二、迭代
另外一種計算n!的方式是：先計算1乘以2，然后用其結果乘以3，再用的到的結果乘以4….一直乘到N。在程序實(shí)現時(shí)，可以定義一個(gè)計數器，每進(jìn)行一次乘法，計數器都自增一次，直到計數器的值等于N截至。代碼如下：
代碼二
int factorial (int n) {
int product = 1;
for(int i=2; i<n; i++) {
product *= i;
}
return product;
}
和代碼一相比，代碼二沒(méi)有構建一個(gè)乘法鏈。在進(jìn)行每一步計算時(shí)，只需要知道當前結果（product）和i的值就可以了。這種計算形式稱(chēng)之為迭代。迭代有這樣幾個(gè)條件：1、有一個(gè)有初始值的變量。2、一個(gè)說(shuō)明變量值如何更新的規則。3、一個(gè)結束條件。（循環(huán)三要素：循環(huán)變量、循環(huán)體和循環(huán)終止條件）。和遞歸一樣。時(shí)間要求隨著(zhù)輸入的增長(cháng)呈線(xiàn)性的可以叫做線(xiàn)性迭代。
三、迭代 VS 遞歸
比較了兩個(gè)程序，我們可以發(fā)現，他們看起來(lái)幾乎相同，特別是其數學(xué)函數方面。在計算n!的時(shí)候，他們的計算步數都是和n的值成正比的。但是，如果我們站在程序的角度，考慮他們是如何運行的話(huà)，那么這兩個(gè)算法就有很大不同了。
�。ㄗⅲ涸闹嘘P(guān)于其區別寫(xiě)的有點(diǎn)扯，這里就不翻譯了，下面是筆者自己總結內容。）
首先分析遞歸，其實(shí)遞歸最大的有點(diǎn)就是把一個(gè)復雜的算法分解成若干相同的可重復的步驟。所以，使用遞歸實(shí)現一個(gè)計算邏輯往往只需要很短的代碼就能解決，并且這樣的代碼也比較容易理解。但是，遞歸就意味著(zhù)大量的函數調用。函數調用的局部狀態(tài)之所以用棧來(lái)記錄的。所以，這樣就可能浪費大量的空間，如果遞歸太深的話(huà)還有可能導致堆棧溢出。
接下來(lái)分析迭代。其實(shí)，遞歸都可以用迭代來(lái)代替。但是相對于遞歸的簡(jiǎn)單易懂，迭代就比較生硬難懂了。尤其是遇到一個(gè)比較復雜的場(chǎng)景的時(shí)候。但是，代碼的難以理解帶來(lái)的有點(diǎn)也比較明顯。迭代的效率比遞歸要高，并且在空間消耗上也比較小。
遞歸中一定有迭代，但是迭代中不一定有遞歸，大部分可以相互轉換。
能用迭代的不要用遞歸，遞歸調用函數不僅浪費空間，如果遞歸太深的話(huà)還容易造成堆棧的溢出。
四、數形遞歸
前面介紹過(guò)，樹(shù)遞歸隨輸入的增長(cháng)的信息量呈指數級增長(cháng)。比較典型的就是斐波那契數列：
用文字描述就是斐波那契數列中前兩個(gè)數字的和等于第三個(gè)數字：0,1,1,2,3,5,8,13,21……
遞歸實(shí)現代碼如下：
int fib (int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
return fib(n-1) + fib(n-2);
}
}
計算過(guò)程中，為了計算fib(5) ，程序要先計算fib(4) 和 fib(3) ，要想計算fib(4) ，程序同樣需要先計算 fib(3) 和 fib(2) 。在這個(gè)過(guò)程中計算了兩次fib(3)。
從上面分析的計算過(guò)程可以得出一個(gè)結論：使用遞歸實(shí)現斐波那契數列存在冗余計算。
就像上面提到的，可以用遞歸的算法一般都能用迭代實(shí)現，斐波那契數列的計算也一樣。
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ì )有冗余計算，可以用迭代來(lái)代替。但是這并不表明遞歸可以完全被取代。因為遞歸有更好的可讀性。
【詳解Java中的迭代和遞歸】相關(guān)文章：
Java中的迭代和遞歸講解08-07
Java中的== 和equals()方法詳解與實(shí)例教程08-03
Java中Class對象詳解09-03
JAVA中toString方法詳解11-03
Java中的對象與引用知識詳解11-07
Java語(yǔ)法基礎中for循環(huán)語(yǔ)句詳解10-10
詳解Java中的Lambda表達式10-20