循環和遞歸

02-03

程序中，遞歸一般是指方法（函數）調用自己。常用的遞歸類型有兩種：

頭遞歸 (head recursion) 是在接近方法開始處發起的遞歸調用。頭遞歸是要處理的第一批內容之一，因為它調用自己，所以它依賴於調用堆棧上執行的上一次操作的結果。因為它使用調用堆棧來處理，所以如果調用堆棧不夠大，則有可能發生堆棧溢出。
尾遞歸 (tail recursion) 是在結尾處執行的遞歸調用，是要處理的最後一行代碼。無論遞歸調用有多深，此方法都不會使用調用堆棧。

我們平時所說的遞歸一般為頭遞歸。

為了更清晰的理解概念，通過代碼分析一下，分別使用頭遞歸、尾遞歸、循環的方式實現階乘方法，下面以5!（5 的階乘）為例做計算。

1.頭遞歸

public long getFactorial(long currNum) { if (currNum == 1) { return 1; } return currNum * getFactorial(currNum - 1); }

每個遞歸調用需要完成並放在遞歸堆棧上，才能計算階乘，以表格表示棧，表格的每一行就是壓到棧里的內容。

棧1 * 12 * f(1)3 * f(2)4 * f(3)5 * f(4)

當currNum=1時，棧達到最大，此時，開始由棧頂層逐級出棧運算，計算順序：

1 * 1 = 1 * 2 = 2 * 3 = 6 * 4 = 24 * 5 = 120

2.尾遞歸

public long getFactorial(long currNum, long sum) { if (currNum == 0) { return sum; } sum *= currNum; return getFactorial(currNum - 1, sum); }

沒有壓棧操作，每次調用都會傳遞本次的計算結果

計算順序:getFactorial(5,1)getFactorial(4,5)getFactorial(3,20)getFactorial(2,60)getFactorial(1,120)getFactorial(0,120)

3.循環

public long getFactorial(long currNum) { long sum = 1; while(currNum > 0 ){ sum *= currNum; currNum--; } return sum; }

循環沒有占操作，執行順序為： 5 * 4 * 3 * 2 * 1 = 120

可以看到尾遞歸和循環已經十分相似了，實際上有些VM也是把尾遞歸轉成循環執行的，但是注意，並不包含SUN的JVM。

4.Q&A

Q.哪一個更好？

A. 不絕對。在一般情形下，循環提供了比遞歸更好的性能，因為方法調用的成本比執行常規語句更高。在使用頭遞歸的情況下，調用堆棧會增加，必須遍歷它才能獲得最終答案。但是，不能否認的是有些場景下，遞歸的性能更好、寫法更優雅。

Q.尾遞歸的好處是什麼？

A. 常規遞歸方法（頭遞歸）會增加調用棧的大小。在尾遞歸中，最後要做的是遞歸，運算在之前就已經完成了。一輪遞歸調用完畢後就沒有其他事情了（除了運算），因此調用時生成的信息也就沒什麼用了。這些無用信息可以丟棄，然後用一組新的參數來調用一次遞歸方法來產生一個新的結果。這也就是說，棧調用減少帶來了內存消耗減少並且程序的性能更好。

Q.什麼情況下應該採用遞歸？

A. 遞歸方法在循環樹結構以及避免醜陋的嵌套循環的情況下是非常好用的，同時需要注意的是，方法必須是收斂的、必須有明確的結束條件、遞歸次數是可預見的。

5.總結

我們怎麼選擇？ 優先使用循環，在滿足以下幾種條件時，可以考慮使用遞歸：

遞歸的語義特別簡明；
執行頻次不高；
遞歸次數可預見且十分有限；
循環的實現寫法特別複雜。