遞歸算法設(shè)計思想與策略分析

周法國++韓智++高天

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

關(guān)鍵詞：遞歸算法；遞歸函數(shù)；算法設(shè)計；程序設(shè)計

DOIDOI：10.11907/rjdk.171715

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

1遞歸算法理論基礎(chǔ)

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

直接遞歸是指函數(shù)在執(zhí)行過程中直接調(diào)用自身；間接遞歸是指函數(shù)在執(zhí)行過程中調(diào)用了其它函數(shù)，再經(jīng)過這些函數(shù)調(diào)用自身。

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

從數(shù)學(xué)角度分析，遞歸的數(shù)學(xué)模型就是遞推原理，在整個過程中，反復(fù)實現(xiàn)的都是同一個原理或操作，其本質(zhì)和數(shù)學(xué)歸納法[3]相同。

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

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

由上述對遞推原理的分析與描述，相應(yīng)地可以得到遞歸求解必須滿足的4個特征：①必須有可最終達到的終止條件，否則程序?qū)⑾萑霟o窮循環(huán)；②子問題的規(guī)模要比原問題小，或更接近終止條件；③子問題可以通過再次遞歸求解或因滿足終止條件而直接求解；④子問題的解應(yīng)能組合為整個問題的解。

2遞歸算法設(shè)計一般方法

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

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

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

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

3遞歸算法示例

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

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

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

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

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

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

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

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

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

gcd（m，n）=gcd（n，m % n）（這里不妨假設(shè)m>n）

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

得到遞歸實現(xiàn)歐幾里得算法求兩個正整數(shù)最大公約數(shù)的函數(shù)如下：

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

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

return m==0？n：m；

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

}

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

int gcd（int m， int n）{//輾轉(zhuǎn)相減法

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

return m；

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

}

例2計算Fibonacci數(shù)

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

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

long long fib（int n）{

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

return n；

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

}

例3有序序列的折半查找

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

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

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歸并排序

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

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遞歸算法復(fù)雜度分析

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

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

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

4.1遞歸樹

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

4.2主定理

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

對形如：T（n）=aT（n/b）+f（n）的遞歸式，其中a≥1，b>1，f（n）漸進趨正，比較f（n）和nlogab，若：①如果存在某常數(shù)ε>0，有f（n）=Θ（nlogab-ε），則T（n）=Θ（nlogab）；②如果f（n）=Θ（nlogablgkn），則T（n）=Θ（nlogablgk+1n）；③如果存在某常數(shù)ε>0，有f（n）=Ω（nlogab+ε），且對常數(shù)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種情況，故其復(fù)雜度分別為Θ（lgn）和Θ（nlgn）；對形如T（n）=4T（n/2）+n的遞歸式，滿足定理第1種情況，故其復(fù)雜度為Θ（n2）；對形如T（n）=4T（n/2）+n3的遞歸式，滿足定理第3種情況，故其復(fù)雜度為Θ（n3）；對形如T（n）=4T（n/2）+n2/lgn遞歸式，則不適用于主定理求解。

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

5遞歸算法非遞歸實現(xiàn)

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

5.1遞歸程序工作原理

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

5.2遞歸算法非遞歸實現(xiàn)方法

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

5.2.1利用循環(huán)實現(xiàn)

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

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

int r=m%n；

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

return n；

}

例2的Fibonacci數(shù)，給出自上而下的遞歸，用遞歸樹分析其復(fù)雜度時，有許多公共字數(shù)，造成重復(fù)計算，導(dǎo)致其復(fù)雜度隨n的增加呈指數(shù)級增長，若采用自下而上的遞歸，有F0，F(xiàn)1，F(xiàn)2，…，F(xiàn)n，則可以得到線性時間復(fù)雜度的算法，可以用如下循環(huán)實現(xiàn)。

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利用棧實現(xiàn)

有些遞歸需要回溯，這就需要使用一些變量存儲中間計算結(jié)果。實際上常常使用棧解決這些問題，如進制轉(zhuǎn)換問題（將一個十進制正整數(shù)轉(zhuǎn)換為其它進制數(shù)），可以利用輾轉(zhuǎn)相除取余數(shù)（逆序）的方法實現(xiàn)，其遞歸函數(shù)描述如下（將十進制整數(shù)n轉(zhuǎ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]；//當前求得的余數(shù)

s[len+1]=0；

}

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

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結(jié)語

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

參考文獻參考文獻：

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

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

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

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

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

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

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

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