Java中的迭代與遞歸實例詳解

這篇文章主要為大家介紹了關於Java中的迭代和遞歸，文章顯示分別介紹了Java中的迭代和遞歸，而後又介紹了迭代和遞歸的區別以及數形遞歸的相關內容，文中介紹的很詳細，相信會對大家學習具有一定的參考借鑒價值，有需要的朋友們可以參考借鑒。

前言

最近在看書的時候看到這一內容，感覺還蠻有收穫的。迭代使用的是循環（for，while，do...wile）或迭代器，當循環條件不滿足時退出。而遞歸，一般是函數遞歸，可以是自身調用自身，也可以是非直接調用，即方法A調用方法B,而方法B反過來調用方法A，遞歸退出的條件為if，else語句，當條件符合基的時候就退出。

上面是迭代和遞歸的語法特性，他們在Java中有什麼不同呢？下面透過這篇文章來詳細了解了解。

一、遞迴

提到迭代，不得不提一個數學表達式: n! =n*(n-1)*(n-2)*...*1

有很多方法可以計算階乘。有一定數學基礎的人都知道n!=n*(n-1)!因此，程式碼的實作可以直接寫成：

程式碼一

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

在執行上述程式碼的時候，其實機器是要執行一系列乘法的： factorial(n) → factorial(n-1) → factorial(n-2) → … → factorial(1) 。所以，需要不斷的追蹤（追蹤上次計算的結果）並呼叫乘法進行計算（建立一個乘法鏈）。這類不斷呼叫自身的運算形式稱之為遞歸。遞歸可以進一步的分為線性遞歸和數形遞歸。資訊量隨著演算法的輸入呈線性成長的遞歸稱為線性遞歸。計算n!（階乘）就是線性遞歸。因為隨著N的增加，計算所需的時間呈線性成長。另外一種資訊量隨著輸入的增長而進行指數增長的稱之為樹形遞歸。

二、迭代

另外一種計算n!的方式是：先計算1乘以2，再用其結果乘以3，再用的到的結果乘以4….一直乘到N。在程式實作時，可以定義一個計數器，每進行一次乘法，計數​​器都會自增一次，直到計數器的值等於N截至。程式碼如下：

程式碼二

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

和程式碼一相比，程式碼二沒有建立一個乘法鏈。在進行每一步計算時，只需要知道當前結果（product）和i的值就可以了。這種計算形式稱為迭代。迭代有這樣幾個條件：1、有一個初始值的變數。 2、一個說明變數值如何更新的規則。 3、一個結束條件。 （循環三要素：循環變數、循環體和循環終止條件）。和遞歸一樣。時間要求隨著輸入的成長呈線性的可以叫做線性迭代。

三、迭代VS 遞歸

比較了兩個程序，我們可以發現，他們看起來幾乎相同，特別是其數學函數方面。在計算n!的時候，他們的計算步數都是和n的值成正比的。但是，如果我們站在程式的角度，考慮他們是如何運作的話，那麼這兩個演算法就有很大不同了。

（註：原文中關於其區別寫的有點扯，這裡就不翻譯了，下面是筆者自己總結內容。）

首先分析遞歸，其實遞歸最大的有點就是把一個複雜的演算法分解成若干相同的可重複的步驟。所以，使用遞歸實現一個計算邏輯往往只需要很短的程式碼就能解決，這樣的程式碼也比較容易理解。但是，遞歸意味著大量的函數呼叫。函數呼叫的局部狀態之所以用堆疊來記錄的。所以，這樣就可能浪費大量的空間，如果遞歸太深的話還有可能導致堆疊溢位。

接下來分析迭代。其實，遞歸都可以用迭代來代替。但相對於遞歸的簡單易懂，迭代就比較生硬難懂了。尤其是遇到一個比較複雜的場景的時候。但是，程式碼的難以理解帶來的有點也比較明顯。迭代的效率比遞歸高，在空間消耗上也比較小。

      遞迴中一定有迭代，但是迭代中不一定有遞歸，且大部分可以互相轉換。

      能用迭代的不要用遞歸，遞迴呼叫函數不只浪費空間，如果遞迴太深的話還容易造成堆疊的溢位。

四、數形遞迴

前面介绍过，树递归随输入的增长的信息量呈指数级增长。比较典型的就是斐波那契数列：

用文字描述就是斐波那契数列中前两个数字的和等于第三个数字：0,1,1,2,3,5,8,13,21……

递归实现代码如下：

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

计算过程中，为了计算fib(5) ，程序要先计算fib(4) 和 fib(3) ，要想计算fib(4) ，程序同样需要先计算 fib(3) 和 fib(2) 。在这个过程中计算了两次fib(3)。

从上面分析的计算过程可以得出一个结论：使用递归实现斐波那契数列存在冗余计算。

就像上面提到的，可以用递归的算法一般都能用迭代实现，斐波那契数列的计算也一样。

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

虽然使用递归的方式会有冗余计算，可以用迭代来代替。但是这并不表明递归可以完全被取代。因为递归有更好的可读性。

以上是Java中的迭代與遞歸實例詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！