3.4　遞歸算法思想

遞歸算法是很常用的算法思想。使用遞歸算法，往往可以簡化代碼編寫，提高程序的可讀性。但是，不合適的遞歸往往導致程序的執行效率變低。

3.4.1　遞歸算法基本思想

遞歸算法即在程序中不斷反復調用自身來達到求解問題的方法。此處的重點是調用自身，這就要求待求解的問題能夠分解為相同問題的一個子問題。這樣，通過多次遞歸調用，便可以完成求解。

遞歸調用是一個方法在其方法體內調用其自身的方法調用方式。這種方法也稱為“遞歸方法”。在遞歸方法中，主調方法又是被調方法。執行遞歸方法將反復調用其自身。每調用一次就進入新的一層。

方法的遞歸調用分兩種情況：直接遞歸和間接遞歸。

?直接遞歸，即在方法中調用方法本身。

?間接遞歸，即間接地調用一個方法，如func_a調用func_b，func_b又調用func_a。間接遞歸用得不多。

編寫遞歸方法時，必須使用if語句強制方法在未執行遞歸調用前返回。如果不這樣做，在調用方法后，它將永遠不會返回。這是一個很容易犯的錯誤。

了解了遞歸方法的設計方法和工作原理后，即可對遞歸的優缺點進行以下總結。

在方法中使用遞歸的好處有：程序代碼更簡潔清晰，可讀性更好。有的算法用遞歸表示要比用循環表示簡潔精練，而且某些問題，特別是與人工智能有關的問題，更適宜用遞歸方法，如八皇后問題、漢諾塔問題等。有的算法，用遞歸能實現，而用循環卻不一定能實現。

遞歸的缺點：大部分遞歸例程沒有明顯地減少代碼規模和節省內存空間。遞歸形式比非遞歸形式運行速度要慢一些。這是因為附加的方法調用增加了時間開銷，例如需要執行一系列的壓棧出棧等操作。但在許多情況下，速度的差別不太明顯。如果遞歸層次太深，還可能導致堆棧溢出。

3.4.2　遞歸算法實例

遞歸算法常用于一些數學計算，或者有明顯的遞推性質的問題。理解遞歸最常用的一個例子是編寫程序求階乘問題。

1.遞歸算法

所謂階乘，就是從1到指定數之間的所有自然數相乘的結果，n的階乘為：

n！=n*（n-1）*（n-2）*……*2*1

而對于（n-1）！，則有如下表達式：

（n-1）！=（n-1）*（n-2）*……*2*1

從上述兩個表達式可以看到階乘具有明顯的遞推性質，即符合如下遞推公式：

n！=n*（n-1）！

因此，可以采用遞歸的思想來計算階乘。遞歸算法計算階乘的代碼示例如下：

其中，輸入參數n為需要計算的階乘。在該方法中，當n<=1時，n！=1；當n>1時，通過遞歸調用來計算階乘。方法fact是一個遞歸方法，在該方法內部，程序又調用了名為fact的方法（即自身）。方法的返回值便是n！。

2.遞歸算法計算階乘

學習了前面的遞歸算法求解階乘問題的算法，下面結合例子來分析一個階乘運算的使用。完整的程序代碼示例如下：

【程序3-3】

該程序中，首先由用戶輸入一個要求階乘的整數，然后調用遞歸方法fact（）來計算階乘。該程序的執行結果，如圖3-3所示。

從上述內容可以看出，使用遞歸算法求解階乘問題的代碼比較簡潔，易于理解。