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