關(guān)于遞歸程序設(shè)計(jì)方法的探討

王筍 耿霞

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

關(guān)鍵詞：遞歸；分治；回溯；漢諾塔問題；N皇后問題

引言

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

1 什么是遞歸

簡單來說，遞歸就是指函數(shù)或者過程在執(zhí)行過程中直接或間接調(diào)用自身的現(xiàn)象。如表1中的函數(shù)即存在遞歸，稱此類發(fā)生自身調(diào)用的函數(shù)為遞歸函數(shù)，通過設(shè)計(jì)遞歸函數(shù)進(jìn)行問題求解的算法稱為遞歸算法。

2 為何用遞歸

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

如一個(gè)正整數(shù)n的階乘可如下定義：

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

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

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

3 如何用遞歸

如上節(jié)所述，進(jìn)行遞歸程序設(shè)計(jì)的關(guān)鍵是借助遞歸關(guān)系的定義和遞歸邊界構(gòu)造遞歸函數(shù)，但有些問題的描述中遞歸關(guān)系和遞歸邊界并沒有顯示給出，稱此類問題為隱式遞歸問題。

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

3.1 降階

若問題規(guī)模較小時(shí)易找到解決方案，則可將此小規(guī)模問題及其解決方案作為遞歸邊界；之后類似數(shù)學(xué)歸納法，假設(shè)規(guī)模為n-1時(shí)會(huì)求解，在此基礎(chǔ)上考慮問題規(guī)模為n時(shí)的解決方案，如此即可得到一個(gè)將大規(guī)模問題歸結(jié)為小規(guī)模問題的遞歸關(guān)系。聯(lián)合遞歸邊界和遞歸關(guān)系的定義便可得到求解問題的遞歸函數(shù)，稱此種構(gòu)造遞歸算法的策略為降階。

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

假設(shè)欲構(gòu)造遞歸函數(shù)Hanoi（n，x，y，z）輸出將n個(gè)盤子從塔座x借助塔座y搬動(dòng)到塔座z上的解決方案。

首先找出遞歸邊界。顯然，當(dāng)問題規(guī)模足夠小如只有一個(gè)盤子時(shí)，可直接將該盤從x搬動(dòng)到y(tǒng)即可，此時(shí)可直接輸出解決方案x→z。由此可得遞歸邊界：

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

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

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

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

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

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

3.2 分治

若操作對(duì)象可定義成由若干結(jié)構(gòu)相同但規(guī)模更小的部分組成，則對(duì)原對(duì)象的操作可遞歸分解到其各組成部分上分別進(jìn)行，如此遞歸分解直到不可再分時(shí)停止，此類求解策略稱為分治。根據(jù)分治策略很容易得到相應(yīng)的遞歸關(guān)系定義和遞歸邊界，從而構(gòu)造出具體的遞歸函數(shù)。

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

3.3 回溯

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

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

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

通過上例可見，回溯法的主要特點(diǎn)是遞歸結(jié)束的條件在搜索的最后一步，關(guān)鍵是找到遞歸邊界條件

4 遞歸存在的問題

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

5 結(jié)束語

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

參考文獻(xiàn)：

[1]譚浩強(qiáng)，《C程序設(shè)計(jì)》，清華大學(xué)出版社，北京：2005.7

[2]孫承愛，趙衛(wèi)東.《程序設(shè)計(jì)基礎(chǔ)（基于C語言）》，清華大學(xué)出版社，北京：2008.2

[3]嚴(yán)蔚敏，吳偉民.《數(shù)據(jù)結(jié)構(gòu)（C語言版）》，清華大學(xué)出版社，北京：2007.3

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

[5]王曉東，《計(jì)算機(jī)算法設(shè)計(jì)與分析》，電子工業(yè)出版社，北京：2007.5