基于分治策略實現模式化構建遞歸函數

楊勇

摘要：遞歸算法在程序設計的許多領域都有重要應用，為了寫出思路清晰，邏輯嚴謹的遞歸函數，以分治策略為基礎，歸納出組成遞歸函數的三大部分：提前終止條件，子問題分解，結果合并。并探討了子問題分解的幾種模式，研究了各種模式下遞歸函數的設計思路，為模式化構建遞歸函數找到可行途徑。

關鍵詞：遞歸;分治策略;子問題分解;回溯;棧區

中圖分類號：TP311.11 文獻標識碼：A

文章編號：1009-3044（2020）01-0264-03

1背景

c語言程序由函數組成，通過函數之間的調用完成程序功能。如果函數在其執行語句中又調用自己，形成函數的遞歸調用。遞歸在數據結構和算法設計領域應用非常廣泛，但函數遞歸調用一直是c語言學習和研究中的一個難點。對遞歸中函數調用順序，函數返回值，遞歸終止條件有許多模糊的，錯誤的認識，不能正確地推理遞歸結果。對運用遞歸方法寫出思路清晰，代碼簡潔的遞歸函數則更視為畏途。本文分析了遞歸過程系統底層運行機理，對編寫遞歸函數的思路做了探討和分析。

2遞歸調用系統底層運行機理

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

函數執行到語句F（a-1）;時，以參數a-1調用自己，系統為F（a01）在棧區空間分配內存，存儲F（a-1）函數的形參和局部變量。F（a-1）函數執行時會再次調用自己，形成循環，這個循環是不能結束的，系統也不斷在棧區為新調用的F函數分配內存。直到棧區空間耗盡。因此必須有一個終止循環調用的機制，我們在函數調用自己的語句之前，設定某種條件，當條件滿足時，函數提前結束。本函數結束了，前面處于等待狀態的函數按調用的逆序逐個結束，整個遞歸也就可以終止。

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

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

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

1）函數遞歸調用時，形參在不斷變化，一般來說，形參的值向縮小的放向變化，直到觸發提前結束函數的條件，當前運行函數不再遞歸，函數按調用的逆序依次結束。

2）每個被調用的遞歸函數都擁有獨立的棧區空間，各函數的形式參數和局部變量處于不同的棧區空間里，相互獨立。

3）整個遞歸調用可以有多個分支，但分支不會同時運行，調用鏈始終為單鏈，只有鏈條末端的函數在運行中，而其他函數則處于暫停狀態。

3運用分治策略構建遞歸函數

遞歸函數解決問題的過程，實際上是算法中分治策略的體現。所謂分治，是把一個復雜問題分解為若干子問題，若子問題有簡單的方法得出解，整個問題的解則是所有子問題解答的合并。如果分解出的子問題仍然不易解決，則繼續對子問題分解，直到分解為能解決的子問題為止，函數遞歸的過程就是對復雜子問題分解的過程。回溯算法也經常使用遞歸來實現。回溯算法中的子問題之間，是相互關聯的，下一個子問題的解依賴于上一個子問題的解。分治算法中的子問題也有一定的關聯性。只是沒有回溯算法中那么緊密。從大的角度來看，回溯算法也屬于分治策略。

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

第一部分：寫出提前終止，不再遞歸的條件。當遞歸函數不斷調用，問題不斷分解，規模不斷縮小，縮小到一定邊界之內，符合一定條件時，此時的子問題是一個最簡子問題，可以直接解決，無須進一步遞歸。條件設定一般由函數形參的變化來完成。

第二部分：問題分解。分解成兩個或多個子問題，簡單子問題直接解決，復雜子問題不能直接解決，交給遞歸函數。解決子問題的算法應該與解決整個問題的算法完全相同，區別只在于處理的規模不同，或處理時的參數不同。要注意的是，子問題分解，有時需要先做一定的前處理工作，之后才能明晰的劃分子問題。

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

遞歸函數三個組成部分中，第二部分如何正確劃分子問題，是設計遞歸函數的關鍵。把子問題分解模式歸納為如下幾種，并按上述三大部分來構建遞歸函數。

3.1問題=1個簡單子問題+1個復雜子問題

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

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

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

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

4）提前結束條件：剩下的子字符串只有一個字符了

5）結果合并：當剩下的字符串只有一個字符時，全排列完成，輸出整個字符串

通過循環把各個字符輪流交換到第一個位置，剩下的少了一個字符的字符串再做全排列，其算法同整個字符串全排列完全相同，交由函數遞歸完成。遞歸調用時，傳給函數的字符串會越來越短，當傳入函數的字符串只有一個字符時，無須再排列，函數提前結束，不進入遞歸。寫出字符串全排列函數如下：

簡單子問題與復雜子問題的結果合并時，要注意合并的順序，有時，復雜子問題的結果要置于簡單子問題的結果之前。例如將整數轉換為字符串輸出，思路如下：

1）問題：整數轉為字符串

2）簡單子問題：把整數的個位轉為字符。（求整數對10的余數可得個位數）

3）復雜子問題：整數去掉個位后的部分整數轉為字符串，遞歸調用求解。

4）提前結束條件：整數只有個位了，直接轉為字符。

5）結果合并：先輸出遞歸函數結果，再輸出個位轉換結果。

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

3.2問題=1個復雜子問題+1個復雜子問題。

這種情況兩個復雜子問題都由函數遞歸解決。然后將兩個子問題的結果合并。合并時有簡單合并，也有經過復雜處理后再合并。例如，求二叉樹的高度，問題分解得：

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

2）復雜子問題一：求二叉樹根的左子樹高度，遞歸調用求解

3）復雜子問題二：求二叉樹根的右子樹高度，遞歸調用求解

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

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

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

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

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

3）劃分子問題：復雜子問題一：對中間數左邊序列排序遞歸調用quicksort

4）劃分子問題：復雜子問題二：對中間數右邊序列排序遞歸調用quicksort

5）左右兩個排序子序列合并。

3.3復雜問題=n個復雜子問題之和

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

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

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

3）提前結束條件，8列皇后都找到位置。或者擺到某一列皇后時，已經找不到合適的行。

4）子問題合并，當8列皇后都能找到位置時，輸出結果。

建立一個數組queens[8]，各元素的下標代表皇后所處的列，各元素的值代表皇后所在的行，遞歸函數只針對子問題求解既可，構建函數如下：

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

4結束語

本文探討了函數遞歸調用操作系統運行機理，梳理出遞歸調用過程的幾個關鍵性特征，歸納出遞歸函數的三大組成部分，并探討了分治策略下問題分解的幾種模式，對每一種模式下構建遞歸函數的思路以具體例子加以分析。以本文總結的遞歸構建模式，可以快速、準確地寫出思路清晰，邏輯嚴密的遞歸函數。