基于分治策略實(shí)現(xiàn)模式化構(gòu)建遞歸函數(shù)

楊勇

摘要：遞歸算法在程序設(shè)計(jì)的許多領(lǐng)域都有重要應(yīng)用，為了寫出思路清晰，邏輯嚴(yán)謹(jǐn)?shù)倪f歸函數(shù)，以分治策略為基礎(chǔ)，歸納出組成遞歸函數(shù)的三大部分：提前終止條件，子問題分解，結(jié)果合并。并探討了子問題分解的幾種模式，研究了各種模式下遞歸函數(shù)的設(shè)計(jì)思路，為模式化構(gòu)建遞歸函數(shù)找到可行途徑。

關(guān)鍵詞：遞歸;分治策略;子問題分解;回溯;棧區(qū)

中圖分類號(hào)：TP311.11 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2020）01-0264-03

1背景

c語言程序由函數(shù)組成，通過函數(shù)之間的調(diào)用完成程序功能。如果函數(shù)在其執(zhí)行語句中又調(diào)用自己，形成函數(shù)的遞歸調(diào)用。遞歸在數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)領(lǐng)域應(yīng)用非常廣泛，但函數(shù)遞歸調(diào)用一直是c語言學(xué)習(xí)和研究中的一個(gè)難點(diǎn)。對(duì)遞歸中函數(shù)調(diào)用順序，函數(shù)返回值，遞歸終止條件有許多模糊的，錯(cuò)誤的認(rèn)識(shí)，不能正確地推理遞歸結(jié)果。對(duì)運(yùn)用遞歸方法寫出思路清晰，代碼簡(jiǎn)潔的遞歸函數(shù)則更視為畏途。本文分析了遞歸過程系統(tǒng)底層運(yùn)行機(jī)理，對(duì)編寫遞歸函數(shù)的思路做了探討和分析。

2遞歸調(diào)用系統(tǒng)底層運(yùn)行機(jī)理

遞歸調(diào)用是一種特殊的函數(shù)嵌套調(diào)用。當(dāng)一個(gè)函數(shù)中某個(gè)語句開始調(diào)用另外一個(gè)函數(shù)時(shí)，在操作系統(tǒng)底層上意味著當(dāng)前正在運(yùn)行的一段執(zhí)行指令序列中途暫停，不往下執(zhí)行，轉(zhuǎn)而去執(zhí)行另一段指令序列。執(zhí)行完畢后，又回到原來執(zhí)行序列的暫停位置處，從暫停位置開始繼續(xù)往下執(zhí)行。每一個(gè)函數(shù)被調(diào)用時(shí)，系統(tǒng)都將為其分配棧區(qū)空間，把函數(shù)形參和局部變量放在棧區(qū)空間里。函數(shù)運(yùn)行結(jié)束，則系統(tǒng)回收為該函數(shù)分配的棧區(qū)內(nèi)存，棧頂指針下移。一個(gè)函數(shù)調(diào)用自己，實(shí)質(zhì)上與函數(shù)去調(diào)用其他函數(shù)沒有任何區(qū)別，也將為之分配獨(dú)立的棧區(qū)空間，放置各自的形參和局部變量。例如F（int a）函數(shù)：

函數(shù)執(zhí)行到語句F（a-1）;時(shí)，以參數(shù)a-1調(diào)用自己，系統(tǒng)為F（a01）在棧區(qū)空間分配內(nèi)存，存儲(chǔ)F（a-1）函數(shù)的形參和局部變量。F（a-1）函數(shù)執(zhí)行時(shí)會(huì)再次調(diào)用自己，形成循環(huán)，這個(gè)循環(huán)是不能結(jié)束的，系統(tǒng)也不斷在棧區(qū)為新調(diào)用的F函數(shù)分配內(nèi)存。直到棧區(qū)空間耗盡。因此必須有一個(gè)終止循環(huán)調(diào)用的機(jī)制，我們?cè)诤瘮?shù)調(diào)用自己的語句之前，設(shè)定某種條件，當(dāng)條件滿足時(shí)，函數(shù)提前結(jié)束。本函數(shù)結(jié)束了，前面處于等待狀態(tài)的函數(shù)按調(diào)用的逆序逐個(gè)結(jié)束，整個(gè)遞歸也就可以終止。

以求斐波那契數(shù)列為例，解析遞歸函數(shù)調(diào)用過程。參數(shù)n為斐波那契數(shù)列的項(xiàng)數(shù)，以0開始，設(shè)n=6，每次調(diào)用以方框表示，畫出調(diào)用圖示：

圖1中實(shí)線箭頭表示調(diào)用方向，數(shù)字表示調(diào)用順序，虛線表示函數(shù)返回位置。調(diào)用過程形成二叉樹的形式，但實(shí)際運(yùn)行時(shí)，這些分支不會(huì)同時(shí)運(yùn)行，調(diào)用中始終只存在單鏈。fibo（6沖進(jìn)入遞歸時(shí)的語句為fibo（5）+fibo（4），實(shí)際上，第二個(gè)函數(shù)調(diào)用fibo（4）并沒有開始，要等到fibo（5）調(diào)用返回后，才會(huì)進(jìn)2k.fibo（4）。依次類推，進(jìn)入fibo（5）后先調(diào)用fibo（4），進(jìn)2k.fibo（4）后先調(diào)用fibo（3），由于fibo（3）滿足提前返回的條件，開始返回，不再遞歸，返回2，回到fibo（4）中，fibo（4）再開始調(diào)用fibo（2），不遞歸，得到結(jié)果1，與fibo（3）的返回結(jié)果相加得3，fibo（4）調(diào)用結(jié)束返回3回到矗一bo（51中，后面調(diào)用過程可作類似分析，不再贅述。

分析遞歸過程的例子，總結(jié)出如下一些特征：

1）函數(shù)遞歸調(diào)用時(shí)，形參在不斷變化，一般來說，形參的值向縮小的放向變化，直到觸發(fā)提前結(jié)束函數(shù)的條件，當(dāng)前運(yùn)行函數(shù)不再遞歸，函數(shù)按調(diào)用的逆序依次結(jié)束。

2）每個(gè)被調(diào)用的遞歸函數(shù)都擁有獨(dú)立的棧區(qū)空間，各函數(shù)的形式參數(shù)和局部變量處于不同的棧區(qū)空間里，相互獨(dú)立。

3）整個(gè)遞歸調(diào)用可以有多個(gè)分支，但分支不會(huì)同時(shí)運(yùn)行，調(diào)用鏈?zhǔn)冀K為單鏈，只有鏈條末端的函數(shù)在運(yùn)行中，而其他函數(shù)則處于暫停狀態(tài)。

3運(yùn)用分治策略構(gòu)建遞歸函數(shù)

遞歸函數(shù)解決問題的過程，實(shí)際上是算法中分治策略的體現(xiàn)。所謂分治，是把一個(gè)復(fù)雜問題分解為若干子問題，若子問題有簡(jiǎn)單的方法得出解，整個(gè)問題的解則是所有子問題解答的合并。如果分解出的子問題仍然不易解決，則繼續(xù)對(duì)子問題分解，直到分解為能解決的子問題為止，函數(shù)遞歸的過程就是對(duì)復(fù)雜子問題分解的過程?；厮菟惴ㄒ步?jīng)常使用遞歸來實(shí)現(xiàn)?；厮菟惴ㄖ械淖訂栴}之間，是相互關(guān)聯(lián)的，下一個(gè)子問題的解依賴于上一個(gè)子問題的解。分治算法中的子問題也有一定的關(guān)聯(lián)性。只是沒有回溯算法中那么緊密。從大的角度來看，回溯算法也屬于分治策略。

以分治策略為基礎(chǔ)，為使求解過程遵循較為固定的步驟，將遞歸函數(shù)大體分為三部分：

第一部分：寫出提前終止，不再遞歸的條件。當(dāng)遞歸函數(shù)不斷調(diào)用，問題不斷分解，規(guī)模不斷縮小，縮小到一定邊界之內(nèi)，符合一定條件時(shí)，此時(shí)的子問題是一個(gè)最簡(jiǎn)子問題，可以直接解決，無須進(jìn)一步遞歸。條件設(shè)定一般由函數(shù)形參的變化來完成。

第二部分：?jiǎn)栴}分解。分解成兩個(gè)或多個(gè)子問題，簡(jiǎn)單子問題直接解決，復(fù)雜子問題不能直接解決，交給遞歸函數(shù)。解決子問題的算法應(yīng)該與解決整個(gè)問題的算法完全相同，區(qū)別只在于處理的規(guī)模不同，或處理時(shí)的參數(shù)不同。要注意的是，子問題分解，有時(shí)需要先做一定的前處理工作，之后才能明晰的劃分子問題。

第三部分：子問題結(jié)果合并。簡(jiǎn)單子問題的解很直觀，而復(fù)雜子問題的解是什么？就是遞歸函數(shù)的返回值（如果沒有返回值，則是函數(shù)運(yùn)行中的所有輸出值），這是理解結(jié)果合并方法的要點(diǎn)。合并可以是子問題的解經(jīng)過簡(jiǎn)單計(jì)算后合并。也可以是復(fù)雜處理運(yùn)算后再合并。

遞歸函數(shù)三個(gè)組成部分中，第二部分如何正確劃分子問題，是設(shè)計(jì)遞歸函數(shù)的關(guān)鍵。把子問題分解模式歸納為如下幾種，并按上述三大部分來構(gòu)建遞歸函數(shù)。

3.1問題=1個(gè)簡(jiǎn)單子問題+1個(gè)復(fù)雜子問題

簡(jiǎn)單子問題直接在函數(shù)中解決，復(fù)雜子問題交由函數(shù)遞歸解決。這是遞歸函數(shù)最常見的問題分解模式。例，求字符串“ABCD”的全排列：

1）問題：輸出字符串全排列。

2）簡(jiǎn)單子問題：字符串第一個(gè)位置作全排列（即字符串中各個(gè)字符輪流放在第1位1

3）復(fù)雜子問題：除開第一個(gè)字符，剩下的子字符串再做全排列，以圖示表示：

4）提前結(jié)束條件：剩下的子字符串只有一個(gè)字符了

5）結(jié)果合并：當(dāng)剩下的字符串只有一個(gè)字符時(shí)，全排列完成，輸出整個(gè)字符串

通過循環(huán)把各個(gè)字符輪流交換到第一個(gè)位置，剩下的少了一個(gè)字符的字符串再做全排列，其算法同整個(gè)字符串全排列完全相同，交由函數(shù)遞歸完成。遞歸調(diào)用時(shí)，傳給函數(shù)的字符串會(huì)越來越短，當(dāng)傳入函數(shù)的字符串只有一個(gè)字符時(shí)，無須再排列，函數(shù)提前結(jié)束，不進(jìn)入遞歸。寫出字符串全排列函數(shù)如下：

簡(jiǎn)單子問題與復(fù)雜子問題的結(jié)果合并時(shí)，要注意合并的順序，有時(shí)，復(fù)雜子問題的結(jié)果要置于簡(jiǎn)單子問題的結(jié)果之前。例如將整數(shù)轉(zhuǎn)換為字符串輸出，思路如下：

1）問題：整數(shù)轉(zhuǎn)為字符串

2）簡(jiǎn)單子問題：把整數(shù)的個(gè)位轉(zhuǎn)為字符。（求整數(shù)對(duì)10的余數(shù)可得個(gè)位數(shù)）

3）復(fù)雜子問題：整數(shù)去掉個(gè)位后的部分整數(shù)轉(zhuǎn)為字符串，遞歸調(diào)用求解。

4）提前結(jié)束條件：整數(shù)只有個(gè)位了，直接轉(zhuǎn)為字符。

5）結(jié)果合并：先輸出遞歸函數(shù)結(jié)果，再輸出個(gè)位轉(zhuǎn)換結(jié)果。

整數(shù)轉(zhuǎn)為字符串一定是前面的部分整數(shù)先輸出，再輸出最后個(gè)位字符，所以遞歸函數(shù)要放在個(gè)位字符輸出之前。再進(jìn)一步思考，如果改變合并順序個(gè)位字符先輸出，遞歸函數(shù)后輸出，那么結(jié)果將得到原整數(shù)的倒序字符串。

3.2問題=1個(gè)復(fù)雜子問題+1個(gè)復(fù)雜子問題。

這種情況兩個(gè)復(fù)雜子問題都由函數(shù)遞歸解決。然后將兩個(gè)子問題的結(jié)果合并。合并時(shí)有簡(jiǎn)單合并，也有經(jīng)過復(fù)雜處理后再合并。例如，求二叉樹的高度，問題分解得：

1）問題：求根為root的二叉樹的高度

2）復(fù)雜子問題一：求二叉樹根的左子樹高度，遞歸調(diào)用求解

3）復(fù)雜子問題二：求二叉樹根的右子樹高度，遞歸調(diào)用求解

4）提前結(jié)束條件：所求樹為空樹，根是NULL，高度為-1;

5）子問題合并：左右兩個(gè)子樹高度的較大值+1為整個(gè)樹的高度

很多情況下，子問題劃分工作并非簡(jiǎn)單明了，必須先做一定的處理，才能開始劃分。例如快速排序法，對(duì)于要排序的數(shù)列，選取一個(gè)中間數(shù)，將其余數(shù)置于中間數(shù)的兩邊，小數(shù)在左邊，大數(shù)在右邊，對(duì)以中間數(shù)為分界的兩個(gè)子序列分別排序，合并起來就是整個(gè)數(shù)列的排序。排序函數(shù)qnisort執(zhí)行過程是：

1）提前返回條件：子序列只有一個(gè)元素

2）子問題劃分前處理：選取中間數(shù)，將其余元素按左小右大的原則分別置于中間數(shù)的兩邊。

3）劃分子問題：復(fù)雜子問題一：對(duì)中間數(shù)左邊序列排序遞歸調(diào)用quicksort

4）劃分子問題：復(fù)雜子問題二：對(duì)中間數(shù)右邊序列排序遞歸調(diào)用quicksort

5）左右兩個(gè)排序子序列合并。

3.3復(fù)雜問題=n個(gè)復(fù)雜子問題之和

如果各復(fù)雜子問題算法相同，但是各子問題傳人參數(shù)與子問題解決的先后順序有關(guān)。這時(shí)可以采取依照一定順序逐個(gè)解決子問題的策略。例如著名的八皇后問題：8x8的國際象棋盤上放上8個(gè)皇后，任意兩個(gè)皇后不能在同一行，列或?qū)蔷€上。問有多少種擺放方法？分析：8個(gè)皇后只能處于不同列上，即一列上只能擺一個(gè)皇后，各列上皇后擺放的行不能相同，對(duì)角線也不能沖突，由此將問題抽象為：在棋盤不同列上為每一個(gè)皇后找到符合條件的行位置，當(dāng)八個(gè)列上都擺上皇后時(shí)，就得到問題的一個(gè)解。

1）問題：依列順序求各列皇后擺放的行

2）問題分解：有8個(gè)子問題，每個(gè)子問題是：給某列上的皇后查找正確的行位置。

3）提前結(jié)束條件，8列皇后都找到位置?；蛘邤[到某一列皇后時(shí)，已經(jīng)找不到合適的行。

4）子問題合并，當(dāng)8列皇后都能找到位置時(shí)，輸出結(jié)果。

建立一個(gè)數(shù)組queens[8]，各元素的下標(biāo)代表皇后所處的列，各元素的值代表皇后所在的行，遞歸函數(shù)只針對(duì)子問題求解既可，構(gòu)建函數(shù)如下：

其中valid_row函數(shù)判斷index列的皇后能否放在某一行上。在eight_queen函數(shù)中，對(duì)于index列的皇后，如果輪詢8個(gè)行位置都找不到符合條件的行位置時(shí)，函數(shù)也將結(jié)束不產(chǎn)生遞歸，此時(shí)函數(shù)將返回到index-1列的函數(shù)循環(huán)中，繼續(xù)查找in-dex-1列皇后下一個(gè)合適的行位置，遞歸則在另一個(gè)分支上繼續(xù)進(jìn)行，所以，eight_queen函數(shù)有兩種終止遞歸的條件。

4結(jié)束語

本文探討了函數(shù)遞歸調(diào)用操作系統(tǒng)運(yùn)行機(jī)理，梳理出遞歸調(diào)用過程的幾個(gè)關(guān)鍵性特征，歸納出遞歸函數(shù)的三大組成部分，并探討了分治策略下問題分解的幾種模式，對(duì)每一種模式下構(gòu)建遞歸函數(shù)的思路以具體例子加以分析。以本文總結(jié)的遞歸構(gòu)建模式，可以快速、準(zhǔn)確地寫出思路清晰，邏輯嚴(yán)密的遞歸函數(shù)。