遞歸算法的設(shè)計(jì)模式與調(diào)試

陳寶平

(內(nèi)蒙古財(cái)經(jīng)學(xué)院信息管理系，內(nèi)蒙古呼和浩特 010070)

一個(gè)直接或間接調(diào)用自己的算法稱(chēng)為遞歸算法。遞歸是軟件設(shè)計(jì)中的重要方法和技術(shù)，其省略了程序設(shè)計(jì)中的許多細(xì)節(jié)操作，簡(jiǎn)化了程序設(shè)計(jì)過(guò)程，遞歸函數(shù)結(jié)構(gòu)清晰，程序易讀[1]。因此，在許多實(shí)際問(wèn)題求解時(shí)，采用遞歸方法要比非遞歸方法容易實(shí)現(xiàn)，特別是在解決樹(shù)、圖等問(wèn)題過(guò)程中得到了廣泛應(yīng)用[2-4]。在計(jì)算機(jī)科學(xué)中，許多數(shù)據(jù)結(jié)構(gòu)都是通過(guò)遞歸方式加以定義的，由于其本身固有的遞歸性質(zhì)，因而關(guān)于它們?cè)S多問(wèn)題的算法均可以采用遞歸技術(shù)加以實(shí)現(xiàn);另外，還有一些問(wèn)題雖然本身沒(méi)有明顯的遞歸特征，但可以利用遞歸技術(shù)設(shè)計(jì)出簡(jiǎn)單高效的算法程序。遞歸問(wèn)題一般采用分治法解決，分治法的設(shè)計(jì)思想是:將一個(gè)難以解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便逐個(gè)擊破，分而治之。文中在分治的基礎(chǔ)上，進(jìn)一步細(xì)化，提出遞歸算法的模型，并通過(guò)一些比較經(jīng)典的實(shí)例加以說(shuō)明。另外，遞歸問(wèn)題在求解的過(guò)程中，如果有錯(cuò)，程序會(huì)中斷，并出現(xiàn)“棧溢出”或“執(zhí)行了非法操作”等信息，這些信息一般是在遞歸算法的某一過(guò)程中出現(xiàn)，調(diào)試難度較大，文中提出使用設(shè)置斷點(diǎn)單步跟蹤及打印變量等方法調(diào)試。

1 遞歸算法的設(shè)計(jì)模式

“自重復(fù)”是遞歸算法所具有的重要特征，對(duì)任何遞歸問(wèn)題，都有向前遞推和向后回退兩個(gè)過(guò)程，把握這兩個(gè)過(guò)程中的關(guān)鍵思維及其終點(diǎn)和起點(diǎn)至關(guān)重要。一般用于遞歸解決的問(wèn)題都是有規(guī)模，有邊界條件的，當(dāng)規(guī)模較大時(shí)，反復(fù)采用分治法手段，可以使子問(wèn)題與原問(wèn)題一致，而其規(guī)模卻不斷縮小，最終使得子問(wèn)題達(dá)到邊界的條件，從而很容易求出解。根據(jù)遞歸問(wèn)題的特點(diǎn)，可設(shè)計(jì)遞歸算法的步驟如下:

(1)找遞歸出口也即邊界條件。對(duì)于一個(gè)遞歸算法而言，遞歸出口非常重要，它是遞歸的終止條件。有的算法邊界條件很明顯，例如Hanoi塔問(wèn)題，盤(pán)子數(shù)為1時(shí)，不需要遞歸。有的算法邊界條件不明顯，此時(shí)可以先進(jìn)行步驟(2)和步驟(3)等，根據(jù)參數(shù)判斷特殊情況，例如整數(shù)劃分問(wèn)題。

(2)把一個(gè)規(guī)模較大的問(wèn)題分解為一個(gè)或若干規(guī)模較小的相似子問(wèn)題。對(duì)于定義本身就是遞歸的問(wèn)題，定義中就包含分治過(guò)程，如樹(shù)結(jié)構(gòu)、圖結(jié)構(gòu)、Fibonaci數(shù)列等，分解過(guò)程很容易。可是對(duì)于沒(méi)有明顯的遞歸特征，但需要用遞歸來(lái)解決的問(wèn)題如Hanoi塔問(wèn)題、迷宮問(wèn)題等，需要編程者自己設(shè)計(jì)遞歸過(guò)程。例如Hanoi塔問(wèn)題，原問(wèn)題是將64個(gè)盤(pán)子從a柱借助b柱移到c柱，可將64個(gè)盤(pán)子問(wèn)題分解為最大盤(pán)子和其余63個(gè)盤(pán)子的問(wèn)題。

(3)定義遞歸過(guò)程。原問(wèn)題與子問(wèn)題一般功能相同，只是規(guī)模或作用的對(duì)象不同，將相似的部分定義為遞歸過(guò)程，例如Hanoi塔問(wèn)題，原問(wèn)題和子問(wèn)題都為從3根柱子上移盤(pán)子，因此將移盤(pán)子定義為遞歸Hanoi函數(shù)。原問(wèn)題與小問(wèn)題中盤(pán)子的個(gè)數(shù)以及3根柱子所承擔(dān)的作用不同，故將3根柱子和盤(pán)子數(shù)n作為Hanoi函數(shù)參數(shù)。最后在確定是否需要返回值，Hanoi塔問(wèn)題只需知道移盤(pán)子的順序，無(wú)需返回值。因此Hanoi塔問(wèn)題的遞歸函數(shù)定義應(yīng)該為:void Hanoi(int n，char x，char y，char z)，其中x，y，z表示3根柱子。

(4)合成解。可以進(jìn)一步推導(dǎo)出遞歸算法的設(shè)計(jì)模式:

其中，“將問(wèn)題規(guī)模N分解為n1，n2，…，nk”，有時(shí)可以通過(guò)算法實(shí)現(xiàn)，有時(shí)直接將N分解即可，不需要調(diào)用算法。經(jīng)過(guò)大量實(shí)踐證明，最好是每個(gè)子問(wèn)題的規(guī)模大致相同，即將一個(gè)問(wèn)題分成大小相等的k個(gè)子問(wèn)題。同樣“合并所有的子問(wèn)題”，需根據(jù)具體的情況而定，有的算法只要將各個(gè)子問(wèn)題分布處理后，原問(wèn)題也隨之解決，這種情況就不需要合并子問(wèn)題。將以上三步合成到遞歸模式中，即可寫(xiě)出程序。

2 實(shí)例

遞歸問(wèn)題一般有3種:問(wèn)題定義本身是遞歸的、數(shù)據(jù)結(jié)構(gòu)是遞歸的和用遞歸解決問(wèn)題。用遞歸解決問(wèn)題，選出3個(gè)經(jīng)典的遞歸算法，說(shuō)明以上理論。

2.1 Hanoi問(wèn)題的解法

Hanoi塔問(wèn)題的求解是講解遞歸程序時(shí)的一個(gè)經(jīng)典示例。根據(jù)遞歸的基本四步和遞歸的模式，可以得到其程序。

Hanoi塔問(wèn)題中，不需要合并子問(wèn)題的結(jié)果，即可求解。

2.2 快速排序問(wèn)題的解法

快速排序的原問(wèn)題是:對(duì)數(shù)組R[1]，R[2]，…，R[n]排序。

(1)若n為0或1，則無(wú)需排序。

(2)否則需要將原問(wèn)題分解，先經(jīng)過(guò)一趟分割使得數(shù)組中的R[pos]有序，隨之大問(wèn)題被分割出兩個(gè)子問(wèn)題，子問(wèn)題一:R[1]，R[2]，…，R[pos-1]排序，子問(wèn)題二:R[pos]，R[pos+1]，…，R[n]排序。

(3)原問(wèn)題和子問(wèn)題相似的是給R數(shù)組排序，不同的是范圍，另外排序無(wú)需返回值，因而定義函數(shù)void QuickSort(ElemType R[]，int low，int high)。

(4)根據(jù)以上分析及遞歸模式可以寫(xiě)出快速排序的算法。

2.3 整數(shù)劃分問(wèn)題的解法

將整數(shù)n表示成一系列正整數(shù)之和，n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整數(shù)的這種表示法稱(chēng)為正整數(shù)n的劃分。正整數(shù)n的不同劃分個(gè)數(shù)稱(chēng)為正整數(shù) n的劃分?jǐn)?shù)，記作p(n)，求p(n)。

(1)此問(wèn)題的邊界條件不明顯，因此先分解。

(2)正整數(shù)n的分解式可能有很多，可以將其分成兩類(lèi):分解式中包含m與分解式中不包含m的，其中最大加數(shù)n1≤m。

(3)原問(wèn)題與子問(wèn)題相同的是求正整數(shù)n的劃分，不同的是n值與m值，另外還需返回分解式的個(gè)數(shù)，故函數(shù)可以定義:int divide_integer(int n，int m)。顯然原問(wèn)題可以設(shè)計(jì)為divide_integer(n，n)，兩個(gè)子問(wèn)題分別設(shè)計(jì)為divide_integer(n-m，m)和divide_integer(n，m-1)。此時(shí)再分析邊界情況:若m=1，則 divide_integer(n，1)=1;若 m＞n，則divide_integer(n，m)=divide_integer(n，n)。

(4)合成程序如下所示:

3 遞歸算法的調(diào)試

遞歸算法的特點(diǎn)是，表面上程序代碼簡(jiǎn)單，但在實(shí)際執(zhí)行流程中，語(yǔ)句執(zhí)行順序頻繁跳躍，難覓規(guī)則，尤其是結(jié)果不正確或代碼在運(yùn)行過(guò)程中斷，這樣的錯(cuò)誤很難調(diào)試。此時(shí)需在代碼中設(shè)計(jì)斷點(diǎn)，使用單步執(zhí)行，觀察各個(gè)變量值、觀察函數(shù)調(diào)用棧等。使用單步跟蹤技術(shù)時(shí)，遞歸算法與非遞歸算法不同之處在于，遞歸算法用到了工作棧，因此需要使用模擬棧。模擬棧一般遵循的規(guī)則是:遞歸調(diào)用需要將參數(shù)、局部變量、執(zhí)行語(yǔ)句的地址等壓棧;遞歸結(jié)束相關(guān)數(shù)據(jù)出棧，并且程序跳回棧中所指的地址。也可在程序中增加若干輸出語(yǔ)句，輸出某些變量的值，以此驗(yàn)證程序的執(zhí)行效果。

遞歸程序在執(zhí)行過(guò)程中，有時(shí)會(huì)因“棧溢出”而中斷，此類(lèi)問(wèn)題可從以下幾個(gè)方面檢查。一是看邊界條件是否考慮齊全，如整數(shù)規(guī)劃問(wèn)題，邊界有4種情況，缺一不可。二是檢查數(shù)據(jù)量，如果數(shù)據(jù)量過(guò)大，也會(huì)造成棧溢出，例如快速排序當(dāng)需排序的數(shù)據(jù)達(dá)到100萬(wàn)時(shí)，就會(huì)出現(xiàn)棧溢出的現(xiàn)象，此時(shí)可以適當(dāng)調(diào)整數(shù)據(jù)的大小。總之遞歸算法的調(diào)試難度較大，需要積累經(jīng)驗(yàn)。

4 結(jié)束語(yǔ)

在分析遞歸算法“自重復(fù)”的重要特征的基礎(chǔ)上，提出一個(gè)通的遞歸算法的設(shè)計(jì)模式，該模式適用大多數(shù)程序設(shè)計(jì)語(yǔ)言。結(jié)合幾個(gè)典型實(shí)例說(shuō)明該模式的應(yīng)用方法和有效性，為研究遞歸算法提供了有效的解決方案，可推廣性強(qiáng)。同時(shí)給出了遞歸程序在調(diào)試過(guò)程中一些方法和技巧。

[1]徐孝凱.數(shù)據(jù)結(jié)構(gòu)實(shí)用教程[M].北京:清華大學(xué)出版社，2004.

[2]嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu):C語(yǔ)言版[M].北京:清華大學(xué)出版社，1997.

[3]周康，同小軍，許進(jìn).基于閉環(huán)DNA模型的八皇后問(wèn)題算法[J].計(jì)算機(jī)工程與應(yīng)用，2007，43(6):4-6.

[4]趙天玉，馬爍.一類(lèi)遞歸關(guān)系模型的求解方法[J].大學(xué)數(shù)學(xué)，2009，25(2):181-184.