本章節由通州北大青鳥校區學術部老師提供：
遞歸的主要優點在于：某些類型的算法采用遞歸比采用迭代算法要更加清晰和簡單。例如快速排序算法按照迭代方法是很難實現的。還有其他一些問題，特別是人工智能問題，就依賴于遞歸提供解決方案。最后，有些人認為遞歸要比迭代簡單。
// A simple example of recursion.
class Factorial {
// this is a recursive function
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("Factorial of 3 is " + f.fact(3));
System.out.println("Factorial of 4 is " + f.fact(4));
System.out.println("Factorial of 5 is " + f.fact(5));
}
}
該程序產生的輸出如下所示：
Factorial of 3 is 6
Factorial of 4 is 24
Factorial of 5 is 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() 語句，顯示每次調用的階數以及中間結果，你會覺得很有意思。
當一個方法調用它自身的時候，堆棧就會給新的局部變量和自變量分配內存，方法代碼就帶著這些新的變量從頭執行。遞歸調用并不產生方法新的拷貝。只有參數是新的。每當遞歸調用返回時，舊的局部變量和自變量就從堆棧中清除，運行從方法中的調用點重新開始。遞歸方法可以說是像“望遠鏡”一樣，可以自由伸縮。
通州北大青鳥校區張老師表示，許多子程序的遞歸版本執行時會比它們的迭代版本要慢一點,因為它們增加了額外的方法調用的消耗。對一個方法太多的遞歸調用會引起堆棧崩潰。因為自變量和局部變量的存儲都在堆棧中，每次調用都創建這些變量新的拷貝，堆棧有可能被耗盡。如果發生這種情況，Java 的運行時系統就會產生異常。但是，除非遞歸子程序瘋狂運行，否則你大概不會擔心這種情況。
通州北大青鳥校區學術部老師強調：當編寫遞歸方法時，你必須使用if條件語句在遞歸調用不執行時來強制方法返回。如果你不這么做，一旦你調用方法，它將永遠不會返回。這類錯誤在使用遞歸時是很常見的。盡量多地使用println() 語句，使你可以了解程序的進程；如果發現錯誤，立即中止程序運行。
下面是遞歸的又一個例子。遞歸方法printArray ( ) 打印數組values 中的前i個元素。
// Another example that uses recursion.
class RecTest {
int values[];
RecTest(int i) {
values = new int[i];
}
// display array – recursively
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
通州北大青鳥校區學術部
