本章節(jié)由通州北大青鳥校區(qū)學(xué)術(shù)部老師提供：
遞歸的主要優(yōu)點在于：某些類型的算法采用遞歸比采用迭代算法要更加清晰和簡單。例如快速排序算法按照迭代方法是很難實現(xiàn)的。還有其他一些問題，特別是人工智能問題，就依賴于遞歸提供解決方案。最后，有些人認為遞歸要比迭代簡單。
// 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));
}
}
該程序產(chǎn)生的輸出如下所示：
Factorial of 3 is 6
Factorial of 4 is 24
Factorial of 5 is 120
如果你對遞歸的方法比較陌生，那么fact( )的操作可能看起來似乎有點糊涂。它是這樣工作的：當(dāng)fact( ) 帶著參數(shù)1被調(diào)用時，該方法返回1；否則它返回fact( n-1 ) 與n的乘積。為了對這個表達式求值，fact() 帶著參數(shù)n-1 被調(diào)用。重復(fù)這個過程直到 n 等于 1，且對該方法的調(diào)用開始返回。
為了更好地理解fact( )方法是如何工作的,通州北大青鳥校區(qū)張老師通過一個短例子來說明。例如當(dāng)計算3 的階乘時，對fact() 的第一次調(diào)用引起參數(shù)2的第二次調(diào)用。這個調(diào)用將引起fact 以參數(shù)1 的第三次調(diào)用，這個調(diào)用返回1，這個值接著與2（第二次調(diào)用時n的值）相乘。然后該結(jié)果（現(xiàn)為2）返回到fact()的最初的調(diào)用，并將該結(jié)果與3（n的初始值）相乘。這時得到答案，6。如果你在fact()中插入println() 語句，顯示每次調(diào)用的階數(shù)以及中間結(jié)果，你會覺得很有意思。
當(dāng)一個方法調(diào)用它自身的時候，堆棧就會給新的局部變量和自變量分配內(nèi)存，方法代碼就帶著這些新的變量從頭執(zhí)行。遞歸調(diào)用并不產(chǎn)生方法新的拷貝。只有參數(shù)是新的。每當(dāng)遞歸調(diào)用返回時，舊的局部變量和自變量就從堆棧中清除，運行從方法中的調(diào)用點重新開始。遞歸方法可以說是像“望遠鏡”一樣，可以自由伸縮。
通州北大青鳥校區(qū)張老師表示，許多子程序的遞歸版本執(zhí)行時會比它們的迭代版本要慢一點,因為它們增加了額外的方法調(diào)用的消耗。對一個方法太多的遞歸調(diào)用會引起堆棧崩潰。因為自變量和局部變量的存儲都在堆棧中，每次調(diào)用都創(chuàng)建這些變量新的拷貝，堆棧有可能被耗盡。如果發(fā)生這種情況，Java 的運行時系統(tǒng)就會產(chǎn)生異常。但是，除非遞歸子程序瘋狂運行，否則你大概不會擔(dān)心這種情況。
通州北大青鳥校區(qū)學(xué)術(shù)部老師強調(diào)：當(dāng)編寫遞歸方法時，你必須使用if條件語句在遞歸調(diào)用不執(zhí)行時來強制方法返回。如果你不這么做，一旦你調(diào)用方法，它將永遠不會返回。這類錯誤在使用遞歸時是很常見的。盡量多地使用println() 語句，使你可以了解程序的進程；如果發(fā)現(xiàn)錯誤，立即中止程序運行。
下面是遞歸的又一個例子。遞歸方法printArray ( ) 打印數(shù)組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);
}
}
該程序產(chǎn)生如下的輸出：
[0] 0
[1] 1
[2] 2
[3] 3
[4] 4
[5] 5
[6] 6
[7] 7
[8] 8
[9] 9
通州北大青鳥校區(qū)學(xué)術(shù)部
