程序調用自身的編程技巧稱為遞歸（recursion），它做為一種算法在程序設計語言中廣泛應用。Java 支持遞歸，在 Java 編程中，遞歸是允許方法調用自身調用的屬性。調用自身的方法稱為是遞歸的。

遞歸的典型例子是數字的階乘。數字 N 的階乘是 1 到 N 之間所有整數的乘積。例如 3 的階乘就是 1×2×3。下面的程序使用遞歸來計算數字的階乘。

public class Factorial {int fact(int n) {int result;if (n == 1) {return 1;}result = fact(n - 1) * n;return result;} } class Recursion {public static void main(String args[]) {Factorial f = new Factorial();System.out.println("3的階乘是 " + f.fact(3));System.out.println("4的階乘是 " + f.fact(4));System.out.println("5的階乘是 " + f.fact(5));} }

該程序產生的輸出如下所示：

3的階乘是 6 4的階乘是 24 5的階乘是 120

如果你對遞歸的方法比較陌生，那么 fact( ) 的操作可能看起來有點糊涂。它是這樣工作的，當 fact( ) 帶著參數 1 被調用時，該方法返回 1，否則它返回 fact( n-1 ) 與 n 的乘積。為了對這個表達式求值，fact( ) 帶著參數 n-1 被調用。重復這個過程直到 n 等于 1，且對該方法的調用開始返回。

為了更好地理解 fact( ) 方法是如何工作的，讓我們通過一個短例子來說明。例如當計算 3 的階乘時，對 fact( ) 的第一次調用引起參數 2 的第二次調用。這個調用將引起 fact 以參數 1的第三次調用，這個調用返回 1，這個值接著與 2（第二次調用時 n 的值）相乘。然后該結果（現為 2）返回到 fact( ) 的最初的調用，并將該結果與 3（n 的初始值）相乘。這時得到答案 6。可以在 fact( ) 中插入 println() 語句，顯示每次調用的階數以及中間結果。

當一個方法調用它自身的時候，堆棧就會給新的局部變量和自變量分配內存，方法代碼就帶著這些新的變量從頭執(zhí)行。遞歸調用并不產生方法新的拷貝。只有參數是新的。每當遞歸調用返回時，舊的局部變量和自變量就從堆棧中清除，運行從方法中的調用點重新開始。遞歸方法可以說是像“望遠鏡”一樣，可以自由伸縮。

許多子程序的遞歸版本執(zhí)行時會比它們的迭代版本要慢一點，因為它們增加了額外的方法調用的消耗。對一個方法太多的遞歸調用會引起堆棧崩潰。因為自變量和局部變量的存儲都在堆棧中，每次調用都創(chuàng)建這些變量新的拷貝，堆棧有可能被耗盡。如果發(fā)生這種情況，Java 的運行時系統(tǒng)就會產生異常。但是，除非遞歸子程序瘋狂運行，否則你大概不會擔心這種情況。

遞歸的主要優(yōu)點在于：某些類型的算法采用遞歸比采用迭代算法要更加清晰和簡單。例如快速排序算法按照迭代方法是很難實現的。還有其他一些問題，特別是人工智能問題，就依賴于遞歸提供解決方案。最后，有些人認為遞歸要比迭代簡單。

當編寫遞歸方法時，你必須使用 if 條件語句在遞歸調用不執(zhí)行時來強制方法返回。如果你不這么做，一旦你調用方法，它將永遠不會返回。這類錯誤在使用遞歸時是很常見的。盡量多地使用 println() 語句，使你可以了解程序的進程。如果發(fā)現錯誤，立即中止程序運行。

下面是遞歸的又一個例子。遞歸方法 printArray( ) 打印數組 values 中的前 i 個元素。

class RecTest {int values[];RecTest(int i) {values = new int[i];}void printArray(int i) {if (i == 0){return;} else {printArray(i - 1);}System.out.println("[" + (i - 1) + "] " + values[i - 1]);} } class Recursion2 {public static void main(String args[]) {RecTest ob = new RecTest(10);int i;for (i = 0; i < 10; i++) {ob.values[i] = i;}ob.printArray(10);} }

該程序產生如下的輸出：

[0] 0 [1] 1 [2] 2 [3] 3 [4] 4 [5] 5 [6] 6 [7] 7 [8] 8 [9] 9

總結

以上是生活随笔為你收集整理的1.27 递归算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。