關于遞歸程序設計方法的探討

王筍 耿霞

摘要：遞歸是一種重要的程序設計方法，但在程序設計過程中一直是個難點。本文以遞歸為中心，從什么是遞歸、為何用遞歸、如何用遞歸以及使用遞歸需要注意的問題四個方面組織全文，從方法論的角度對遞歸程序設計進行系統的闡述。文中不僅介紹了遞歸程序設計的一般步驟和方法，還介紹了如何通過降階、分治和回溯等策略進行遞歸程序設計。

關鍵詞：遞歸；分治；回溯；漢諾塔問題；N皇后問題

引言

遞歸在程序設計基礎、數據結構以及算法設計與分析等方面都占用重要地位，是一類重要的程序設計方法，但遞歸程序設計一直是個難點。程序設計過程通常會對為何用遞歸、如何用遞歸以及遞歸程序的執行過程存在疑惑。究其原因，一方面是通常只將遞歸作為一個概念進行簡單介紹，對遞歸的執行過程以及遞歸程序設計的一般性步驟和方法描述過少；更重要的是缺少對遞歸程序設計方法系統性的概述。本文旨在解決這一問題，全文以遞歸為中心，從什么是遞歸、為何用遞歸、如何用遞歸以及使用遞歸需要注意的問題四個方面組織全文，從方法論的角度對遞歸程序設計進行系統的闡述。文中一方面結合漢諾塔問題和N皇后問題等經典實例介紹了遞歸程序設計的一般步驟和方法，還介紹了如何通過降階、分治和回溯等策略進行遞歸程序設計。

1 什么是遞歸

簡單來說，遞歸就是指函數或者過程在執行過程中直接或間接調用自身的現象。如表1中的函數即存在遞歸，稱此類發生自身調用的函數為遞歸函數，通過設計遞歸函數進行問題求解的算法稱為遞歸算法。

2 為何用遞歸

很多問題可以用遞歸的形式來描述，此時用遞歸進行程序設計簡單、方便、易懂。

如一個正整數n的階乘可如下定義：

在上述定義中，F（n）=n*F（n-1）在數學中稱為遞歸公式，實際就對應程序設計中的遞歸調用，F（1）=1稱為遞歸邊界。根據階乘的這種定義，只需列出遞歸邊界和遞歸公式，再加上必須的函數頭、變量聲明等語句便可得到一個遞歸函數，如表1所示。需要說明的是，如此輕而易舉得到的遞歸函數可直接求出n的階乘，下面分析遞歸函數的執行過程予以證實。

假設主函數代碼如表2所示，欲求3！并輸出。當主函數執行到x=F（3）時，函數F第一次被調用并開始執行，此時形參n=3，顯然應執行語句result=3*F（2）；之后F第二次被調用并開始執行，此時形參n=2，顯然應執行語句result=2*F（1）；之后F第三次被調用并開始執行，此時形參n=1，顯然應執行語句result=1和return result，至此，函數F的第三次執行結束，返回至調用語句result=2*F（1），注意返回后流程位于F的第二次執行中；繼續執行可得result=2*1，接下來執行return result，至此，函數的第二次執行也結束并返回至調用語句result=3*F（2）處，注意返回后流程位于F的第一次執行中；繼續執行得result=3*2*1，接下來執行語句return result，至此函數的第一次執行結束，返回至調用語句x=F（3）處，此時流程已回到主函數中；繼續執行得x=3*2*1，如此3！被求出并賦予x，最后輸出x的值6，整個程序結束。

由上例可見，遞歸通常是把一個大型復雜的問題層層轉化為一個與原問題本質相同但規模更小的子問題來求解，運用遞歸只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量，用遞歸思想寫出的程序往往十分簡潔易懂。

3 如何用遞歸

如上節所述，進行遞歸程序設計的關鍵是借助遞歸關系的定義和遞歸邊界構造遞歸函數，但有些問題的描述中遞歸關系和遞歸邊界并沒有顯示給出，稱此類問題為隱式遞歸問題。

對于顯示遞歸問題，如前所述，直接根據遞歸關系的定義和遞歸邊界構造出遞歸函數即可求解；對于隱式遞歸問題則要通過一定的策略來找出隱藏的遞歸關系和遞歸邊界，常見策略如降階、分治和回溯。

3.1 降階

若問題規模較小時易找到解決方案，則可將此小規模問題及其解決方案作為遞歸邊界；之后類似數學歸納法，假設規模為n-1時會求解，在此基礎上考慮問題規模為n時的解決方案，如此即可得到一個將大規模問題歸結為小規模問題的遞歸關系。聯合遞歸邊界和遞歸關系的定義便可得到求解問題的遞歸函數，稱此種構造遞歸算法的策略為降階。

下面以漢諾塔問題為例說明如何通過降階構造遞歸函數。所謂漢諾塔問題是指梵塔內有ABC三個塔座，其中塔座A上插有n個由小到大羅列的圓盤?，F要求將這些圓盤從塔座A上搬動到塔座C上，要求一次只能搬動一個盤子，而且要求大盤不能壓小盤，中間允許借助塔座B臨時存放盤子。

假設欲構造遞歸函數Hanoi（n，x，y，z）輸出將n個盤子從塔座x借助塔座y搬動到塔座z上的解決方案。

首先找出遞歸邊界。顯然，當問題規模足夠小如只有一個盤子時，可直接將該盤從x搬動到y即可，此時可直接輸出解決方案x→z。由此可得遞歸邊界：

if（n==1）printf（“%c→%c”，x，z）。

接下來找遞歸關系。當n>1時，假設n-1個盤子能按規則要求從一個塔座借助另一個塔座搬動到第三個塔座上，則要將n個盤子從塔座x借助y搬動到z可分為三步：首先將塔座x上前n-1個小盤從塔座x借助塔座z搬動到塔座y上，之后將塔座x上僅剩的盤子從x搬動z上，最后將塔座y上n-1個盤子從塔座y借助塔座x搬到塔座z上。由此可得遞歸關系：

Hanoi（n-1，x，z，y）；

printf（“%c→%c”，x，z）；

Hanoi（n-1，y，x，z）；

根據上述遞歸邊界和遞歸關系顯然可得求解Hanoi塔問題的遞歸函數如表3所示。如執行語句Hanoi（3，A，B，C）將輸出：A→C A→B C→B A→C B→A B→C A→C

3.2 分治

若操作對象可定義成由若干結構相同但規模更小的部分組成，則對原對象的操作可遞歸分解到其各組成部分上分別進行，如此遞歸分解直到不可再分時停止，此類求解策略稱為分治。根據分治策略很容易得到相應的遞歸關系定義和遞歸邊界，從而構造出具體的遞歸函數。

如非空的二叉樹可看作為由根結點、根節點的左子樹以及根結點的右子樹三部分組成，每一部分又都是一顆樹。如右圖所示二叉樹T可看作由根節點A、結點B、C構成的左子樹和結點D、E、F構成的右子樹組成。欲設計遞歸函數NodeCount（T）求二叉樹T的結點總數，顯然T的結點數是T的左子樹結點數與T的右子樹結點數之和再加1，這實際就是遞歸關系的定義；再注意到空樹的結點樹為0，依次作遞歸邊界，即可得到表4所示所示的樹結點計數的遞歸函數。

3.3 回溯

回溯也是一種問題求解策略，通常指讓計算機從某種可能的情況出發自動向前進行搜索，碰到符合的情況就輸出或者保存起來，在一條路徑上走到“盡頭”后就回到原來的岔路口選擇一條以前沒有走過的路重新向前進行探測，直到找到解或者走完所有路徑為止?；厮菥唧w編程實現時通常都用遞歸：“向前進行搜索”對應遞歸調用，“盡頭”對應遞歸邊界。

比如N皇后問題。題目是說，一個N*N的國際象棋棋盤上主放置N個皇后，使其不能相互攻擊，即任何兩個皇后都不能處在棋盤的同一行、同一列、同一條斜線上，要求輸出所有可能的擺放方案。其實，題目就是要找出所有可能的合法情況，可以考慮用回溯法求解。

讓計算機逐行前進，每行擺放一個棋子，若合法則前進到下一行。為此可設遞歸函數void NQueens（int arr[N][N]，int i）；第一個參數代表棋盤，第二個參數代表目前標號為0的行到標號為i-1的行已經各有一個棋子，且符合規則要求。遞歸函數第一次被調用時時形參i值應為0，函數體內遞歸調用語句應為NQueens（arr，i+1）。至此遞歸關系定義已經找到，但還有一個問題，即遞歸何時停止或者說計算機前進過程中如何判斷是否 “走到盡頭”。分析可見共有兩種情況：其一，當前行下完一個棋子后出現了非法情況，如同一列或同一斜線上出現了多個皇后，此時應抹掉該行所下棋子，在其右側重新下一個棋子再重新檢查；其二，當前行下完一個棋子后仍然合法，但恰巧當前行是最后一行，這實際意味著已經得到了一種合法的擺放方案，此時應輸出該方案，之后抹掉該行所下棋子，在其右側下一個棋子重新檢查。由上述遞歸邊界和遞歸關系定義可構造遞歸函數如下：

通過上例可見，回溯法的主要特點是遞歸結束的條件在搜索的最后一步，關鍵是找到遞歸邊界條件

4 遞歸存在的問題

使用遞歸進行程序設計思路清晰、代碼簡潔，但遞歸調用過程中，每一次發生調用系統都要將返回地址、局部變量等信息入棧保存，因此，遞歸程序的運行效率較低，而且遞歸次數過多還容易造成棧溢出。此外，尤其要避免重復遞歸調用的現象發生。比如求Fibnacci數列的第n項可通過表6所示遞歸函數實現，假設n=4則遞歸執行過程中發生的遞歸調用如圖3所示，可見n=4時f（1）已經被重復調用了3次。在Core 2CPU T5500、內存1G的機器上進行測試，計算f（40）約需20.374秒的時間，其主要原因在于計算f（40）時f（1）會被重復調用165580141次；而計算f（50）更是需要40多分鐘！

5 結束語

本文系統講述了遞歸的基本概念、使用遞歸進行程序設計的好處以及如何設計遞歸程序，結合Hanoi塔問題、N皇后問題等經典實例介紹了通過降階、分治及回溯構造遞歸函數的一般化方法，并對遞歸使用過程中可能存在的問題進行了說明?？偟貋碚f，遞歸作為一種重要的程序設計方法可使得編碼清晰易懂，但存在運行效率較低的問題，在實際應用當中，建議僅當傳統方法不方便求解時使用遞歸。

參考文獻：

[1]譚浩強，《C程序設計》，清華大學出版社，北京：2005.7

[2]孫承愛，趙衛東.《程序設計基礎（基于C語言）》，清華大學出版社，北京：2008.2

[3]嚴蔚敏，吳偉民.《數據結構（C語言版）》，清華大學出版社，北京：2007.3

[4]M.A.Weiss著，翁惠玉等譯.《數據結構與問題求解-Java語言描述）》，人民郵電出版社，北京：2006.7

[5]王曉東，《計算機算法設計與分析》，電子工業出版社，北京：2007.5