遞歸算法設計思想與策略分析

周法國++韓智++高天

摘要：遞歸作為一種算法設計策略，是程序設計和描述算法的一種有力工具，在程序設計中被廣泛應用。尤其在數值計算、數據結構、人工智能、算法設計與分析等領域應用廣泛。分析遞歸算法設計的一般思想與方法、步驟及需要解決的關鍵問題。通過幾個經典的可以采用遞歸實現的算法，詳細闡述了如何通過分析問題，找到遞歸實現的兩個基本核心問題，即遞歸表達式和遞歸終止條件，并據此編寫遞歸調用函數。

關鍵詞：遞歸算法；遞歸函數；算法設計；程序設計

DOIDOI：10.11907/rjdk.171715

中圖分類號：TP312文獻標識碼：A文章編號：16727800（2017）010003504

1遞歸算法理論基礎

眾所周知，通常把程序調用自身的編程技巧稱為遞歸[1]，遞歸作為一種算法設計策略，在程序設計中得到了廣泛應用。遞歸按照調用的方式，可分為直接遞歸和間接遞歸兩種類型[2]。

直接遞歸是指函數在執行過程中直接調用自身；間接遞歸是指函數在執行過程中調用了其它函數，再經過這些函數調用自身。

遞歸從字面上看，包含兩部分內容，它由兩個字組成，即“遞”和“歸”，“遞”表示傳送、傳達的意思，“歸”是返回的意思，從字面上講遞歸就是周而復始的循環，但又不是簡單的循環。

從數學角度分析，遞歸的數學模型就是遞推原理，在整個過程中，反復實現的都是同一個原理或操作，其本質和數學歸納法[3]相同。

遞歸適用于下述問題：解決一個問題可以轉化為解決其子問題，而其子問題又變成子問題的子問題，而且這些問題的解決都是采用同一個模型，也即需要解決的問題和其子問題具有相同的邏輯歸納處理項。有一個子問題是例外的，也即遞歸結束的那一項，處理方法不適用于上述歸納處理項，當然也不能用這種方法去處理，否則就形成了無窮遞歸。這就引出了一個歸納終結點以及直接求解的表達式。

根據上述分析，遞推可表示如下：①步進表達式：問題轉換為子問題求解的表達式；②結束條件：不再適用于步進表達式的情況，亦即何時不再使用步進表達式；③直接求解表達式：在結束條件下能夠直接計算返回值的表達式；④邏輯歸納項：適用于一切非結束條件下子問題的處理，包含上述步進表達式。

由上述對遞推原理的分析與描述，相應地可以得到遞歸求解必須滿足的4個特征：①必須有可最終達到的終止條件，否則程序將陷入無窮循環；②子問題的規模要比原問題小，或更接近終止條件；③子問題可以通過再次遞歸求解或因滿足終止條件而直接求解；④子問題的解應能組合為整個問題的解。

2遞歸算法設計一般方法

根據上述分析，遞歸的基本思想是將規模大的問題轉化為規模較小的相似子問題加以解決，且這些規模較小子問題的求解過程相對容易，同時規模較小子問題的解足以構成原問題的解。

在算法（函數）實現時，由于解決大問題的方法和解決小問題的方法往往是同一個方法，因此產生了函數調用其自身的情況。解決問題的函數必須有明確的結束條件，也即遞歸函數必須是收斂的[5]，這樣才可以避免出現無窮遞歸的情況。

綜上，求解遞歸問題可轉化為求解如下3方面問題：①如何將原問題劃分為規模更小的子問題；②遞歸終止條件及最小子問題求解方法（遞歸函數的出口，允許遞歸函數有多個出口，至少要有1個）；③找到保證遞歸規模向出口靠攏的表達式。

將遞歸求解滿足的4個特征歸結為解決上述3個問題。實質上，上述3個問題還可作進一步簡化，遞歸問題求解的兩個關鍵點就是找到遞歸關系式和找出遞歸終止條件。

3遞歸算法示例

函數的遞歸調用是程序設計教學中的一個難點問題，在此，本文通過由淺入深的實例，引導學生逐步掌握使用遞歸思想進行程序設計的技巧與能力。

例1計算兩個正整數m和n的最大公約數

最大公約數，也稱為最大公因數或最大公因子，指兩個或多個正整數中約數最大的那一個。其主要求解方法有：質因數分解法、短除法、輾轉相除法（歐幾里得算法）[4]、更相減損法等。

質因數分解法，就是對兩個正整數分別分解質因數，再把兩個數中所有公有的質因數提出來連乘，所得到的積就是這兩個數的最大公約數。按照上述算法原理，正整數的質因數分解、求兩個整數的公有質因數都很難分解為規模更小、求法類似的子問題，因此無法用遞歸解決。經過類似分析，短除法、更相減損法也都不能遞歸地實現。

Knuth在《計算機程序設計藝術》第一卷中給出了求兩個正整數m和n最大公約數的歐幾里德算法，其描述如下：

Step1：求余數：用n除m，令r為余數（這里0≤r

Step2：如果r=0，算法終止，n就是答案；

Step3：置m←n，n←r，然后返回Step1。

歐幾里得算法計算原理依據如下結論：兩個正整數的最大公約數（Greatest Common Divisor，gcd）等于較小的那個數和兩數相除余數的最大公約數。亦即：

gcd（m，n）=gcd（n，m % n）（這里不妨假設m>n）

這樣就把求解兩個正整數m和n的最大公約數轉換為求解更小的兩個數n和m%n的最大公約數（1），當m和n有一個數為0，另一個數就是所求的最大公約數（2），（1）和（2）正好對應了遞歸求解的兩個核心問題：遞歸表達式和遞歸終止條件。

得到遞歸實現歐幾里得算法求兩個正整數最大公約數的函數如下：

int gcd（int m， int n）{//歐幾里得算法（輾轉相除法）

if（m*n==0）//遞歸終止的條件

return m==0？n：m；

return gcd（n， m%n）；//遞歸表達式

}

與輾轉相除法類似，可以利用輾轉相減法求兩個正整數的最大公約數，仍然采用遞歸方法實現，本文給出具體遞歸函數。

int gcd（int m， int n）{//輾轉相減法

if（m==n）//遞歸終止的條件

return m；

return gcd（ m-n<0？n-m：m-n， m

}

例2計算Fibonacci數

Fibonacci數列又稱為黃金分割數列，指如下數列：1，1，2，3，5，8，13，21，…。在數學上，Fibonacci數列被以如下形式遞歸定義：F0=0，F1=1，Fn=Fn-1+Fn-2（n>=2）。

上述定義給出了遞歸求解Fibonacci數列的終止條件和遞歸表達式，可以很簡單地得到如下遞歸函數：

long long fib（int n）{

if（n==0 ‖ n==1）//遞歸終止的條件

return n；

return fib（n-1）+fib（n-2）；//遞歸表達式

}

例3有序序列的折半查找

折半查找，也稱二分查找，是針對順序存儲且已經有序排序的數據進行快速查找的一種算法，其基本思想是將n個元素分成大致相等的兩部分，取a[n/2]與x做比較，如果x=a[n/2]，則找到x，算法中止；如果xa[n/2]，則只需在數組a的右半部搜索x。

由上分析即可得到遞歸終止的條件是：待查找元素是查找區間的中點元素（查找成功）或者查找區間不存在（查找失敗），即可得到折半查找的遞歸函數如下：

int binarysearch（int a[]， int low， int high， int x）{

while（p<=q）{

int mid = （low+high）/2；

if（a[mid]==x） return mid； //查找成功，遞歸終止的條件

if（x

return binarysearch（a， low， mid-1，x）； //遞歸表達式

else

return binarysearch（a， mid+1， high， x）； //遞歸表達式

}

return -1；//查找失敗，遞歸終止的條件

}

例4歸并排序

歸并排序是建立在歸并操作上的一種有效穩定的排序算法，該算法是分治法的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列，即先使每個子序列有序，再使子序列段間有序。針對一個無序序列，根據該算法，可以先將該序列分成大小基本相當的兩個子序列，并使之有序，再使用歸并方法將兩個有序的子序列合并成一個有序序列，針對子序列的排序方法仍然可以遞歸地使用此算法，直到子序列的長度為1時，自動有序，即可得到歸并排序的遞歸函數如下：

void mergesort（int a[]， int low， int high）{

if（low

int mid=（low+high）/2；

mergesort（a，low，mid）；//遞歸表達式

mergesort（a，mid+1，high）；//遞歸表達式

merge（a，low，mid，high）；//有序序列的歸并操作[7]

}

}

4遞歸算法復雜度分析

算法的時間復雜度指計算機執行該算法所需時間，反映程序執行時間隨輸入規模（記為n）增長而增長的量級，可在很大程度上反映出算法的優劣。實際上，往往在問題規模區域無窮大時（n→∞）分析最壞情況下的時間復雜度。稱為算法的漸進時間復雜度，復雜度函數一般表示成問題規模n的函數，用T（n）表示。

例1中求兩個正整數最大公約數的時間復雜度為T（m，n）=T（n， m%n）+O（1），例2中求Fibonacci數的時間復雜度為T（n）=T（n-1）+T（n-2）+Θ（1），例3中折半查找的時間復雜度為T（n）=T（n/2）+Θ（1），例4中歸并排序的時間復雜度為T（n）=2T（n/2）+Θ（n）。

對于遞歸算法的時間復雜度分析主要有3種方法：代換法[6]、遞歸樹法和主定理方法。本文主要介紹遞歸樹法和主定理方法。

4.1遞歸樹

遞歸樹法主要是將遞歸式轉換成樹的形式，然后利用樹的數學概念和特性得知樹高和葉子節點個數，從而求解出算法復雜度。這種方法更合適去驗證自己的結論，因為它是一種嚴格的證明過程。下面以一個具體遞歸式介紹遞歸樹法求解算法時間復雜度的過程，以T（n）=T（n/4）+T（n/2）+Θ（n）為例：

4.2主定理

主定理方法是一種針對遞歸策略的算法分析方法，可以瞬間估算出算法復雜度，主定理描述如下：

對形如：T（n）=aT（n/b）+f（n）的遞歸式，其中a≥1，b>1，f（n）漸進趨正，比較f（n）和nlogab，若：①如果存在某常數ε>0，有f（n）=Θ（nlogab-ε），則T（n）=Θ（nlogab）；②如果f（n）=Θ（nlogablgkn），則T（n）=Θ（nlogablgk+1n）；③如果存在某常數ε>0，有f（n）=Ω（nlogab+ε），且對常數c>0與所有足夠大的n，有af（n/b）≤cf（n），則T（n）=Θ（f（n））。

該定理可以采用遞歸樹法直觀地加以證明，在此不再贅述。

針對折半查找的遞歸式T（n）=T（n/2）+Θ（1）和歸并排序的遞歸式T（n）=2T（n/2）+Θ（n）均滿足定理的第2種情況，故其復雜度分別為Θ（lgn）和Θ（nlgn）；對形如T（n）=4T（n/2）+n的遞歸式，滿足定理第1種情況，故其復雜度為Θ（n2）；對形如T（n）=4T（n/2）+n3的遞歸式，滿足定理第3種情況，故其復雜度為Θ（n3）；對形如T（n）=4T（n/2）+n2/lgn遞歸式，則不適用于主定理求解。

上述例題中輾轉相除法的時間復雜度和折半查找相近，T（n）=T（n-1）+T（n-2）+Θ（1）遞歸式的時間復雜度是指數階的。

5遞歸算法非遞歸實現

遞歸就是函數直接調用自己或通過一系列調用語句間接調用自己的過程，是一種描述問題和解決問題的基本方法。遞歸算法實際上是一種基于分治的方法，它把復雜問題分解為簡單問題來求解。對于很多復雜問題（例如hanio塔問題），遞歸算法是一種自然且合乎邏輯的問題解決方式，但是遞歸算法的執行效率通常較差，往往需要將遞歸算法轉換為非遞歸算法。

5.1遞歸程序工作原理

一個遞歸函數的調用過程類似于多個函數的嵌套調用，只不過調用函數和被調用函數是同一個函數。為了保證遞歸函數的正確執行，系統需設立一個工作棧。具體而言，遞歸調用的內部執行過程如下：①開始執行時，首先為遞歸調用建立一個工作棧，其結構包括值參、局部變量和返回地址；②每次執行遞歸調用之前，把遞歸函數的值參和局部變量的當前值以及調用后的返回地址入棧；③每次遞歸調用結束后，將棧頂元素出棧，使相應的值參和局部變量恢復為調用前的值，然后轉向返回地址指定的位置繼續執行。

5.2遞歸算法非遞歸實現方法

基于上述遞歸程序工作原理，一種遞歸求解算法不需要回溯，可以通過迭代或循環直接求解；一種需要回溯，不能直接求解，需要利用棧保存中間計算結果。由此得到兩種遞歸算法的非遞歸實現方法：利用循環實現和利用棧實現。

5.2.1利用循環實現

很多遞歸程序都可以使用循環實現，如例1介紹的歐幾里得算法，可以很方便地使用循環解決。

int gcd（int m， int n）{//歐幾里德算法

int r=m%n；

while（r）{m=n；n=r；r=m%n；}

return n；

}

例2的Fibonacci數，給出自上而下的遞歸，用遞歸樹分析其復雜度時，有許多公共字數，造成重復計算，導致其復雜度隨n的增加呈指數級增長，若采用自下而上的遞歸，有F0，F1，F2，…，Fn，則可以得到線性時間復雜度的算法，可以用如下循環實現。

int fib（int n）{//

int f0=0，f1=1，f，k=2；；

while（k++<=n）{f =f0+f1；f0=f1；f1=f；}

return f；

}

5.2.2利用棧實現

有些遞歸需要回溯，這就需要使用一些變量存儲中間計算結果。實際上常常使用棧解決這些問題，如進制轉換問題（將一個十進制正整數轉換為其它進制數），可以利用輾轉相除取余數（逆序）的方法實現，其遞歸函數描述如下（將十進制整數n轉化為b進制字符串s）：

void numconv（char*s， int n， int b）{

int len；

if（n==0）{strcpy（s，“”）；return；}//遞歸終止的條件

numconv（s，n/b，b）；//遞歸表達式

len=strlen（s）；

s[len]=“0123456789ABC…XYZ”[n%b]；//當前求得的余數

s[len+1]=0；

}

非遞歸實現時，需要將每次求得的余數所對應的字符先存儲起來，到程序結束時再逆向依次取出即可組成所得到的字符串，采用《數據結構（C語言版）》[7]中棧（字符棧）的結構描述及相關操作方法，即可得到非遞歸算法描述如下：

void numconvert（char*s， int n， int b） {

SqStack S；

InitStack（S）；

while（n）{

char c=“0123456789ABC…XYZ”[n%b]；

Push（S， c）；

}

while（！StackEmpty（S））{//回溯

char c； int i=0；

Pop（S，c）；

s[i++]=c；

}

s[i]=0；

}

6結語

本文介紹了遞歸算法的理論基礎、一般方法，闡述了遞歸算法的復雜度分析方法以及遞歸算法非遞歸實現的兩種方法。遞歸可以簡化程序設計，提高代碼可讀性，但往往會增加時間開銷，使得系統具有較高的時間復雜度。相應的非遞歸函數雖然效率高，但編寫起來比較困難，而且相對而言程序代碼的可讀性、可維護性較差。隨著計算機硬件性能的不斷提高，程序在很多場合優先考慮的是可讀性而不是高效性，因此應鼓勵在必要情況下使用遞歸思想實現相關程序設計。

參考文獻參考文獻：

[1]譚浩強.C程序設計[M].第4版.北京：清華大學出版社，2010.

[2]吳曉晨.遞歸程序設計教學方法的研究[J].天津科技，2017，44（1）：6973.

[3]馮立坤，劉影.數學歸納法的若干應用[J].佳木斯大學學報：自然科學版，2016，34（4）：636637.

[4]高德納.計算機程序設計藝術（卷1）：基本算法[M].第3版.李伯民，范明，蔣愛軍，譯.北京：人民郵電出版社，2016.

[5]王海深，馬洪英.遞歸程序設計的理論基礎探討[J].小型微型計算機系統，1997，19（2）：7780.

[6]THOMAS HCORMEN，CHARLES ELEISERSON，RONALD LRIVEST，et al.Introduction to algorithms[M]. Massachusetts：The MIT Press，2009.

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

責任編輯（責任編輯：孫娟）endprint