遞歸算法應(yīng)用分析

摘要：遞歸算法是程序設(shè)計中一種重要的方法，對于一些看起來很復(fù)雜的問題，使用遞歸方法可以提供非常優(yōu)雅和簡潔的解決方案，而且解題思路清晰、代碼量小。但是遞歸算法的設(shè)計有幾個需要注意的關(guān)鍵點，如果不能很好的解決，則無法在程序設(shè)計中體現(xiàn)遞歸的強(qiáng)大功能。該文通過兩個示例說明設(shè)計遞歸算法中需要關(guān)注的關(guān)鍵點及其解決辦法。

關(guān)鍵詞：算法；遞歸；返回值；參數(shù)

中圖分類號：TP312文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2008)28-0107-04

Analysis of JUnit Framework

DAI Jian-guo，CAO Chuan-dong， GUO Li

(College of Information Science and Technology，Shihezi University，Shihezi 832000，China)

Abstract: Recresive Algorithm is an important technology in programming， To some complicated problem， we could get very elegant solution with less amounts of codes by using recursive algorithm. There are several key points in recursive algorithm designation which must solve， the paper explains the key points and the solutions with two examples.

Keywords: algorithm; recursive; return value; parameter

1 引言

遞歸算法是程序設(shè)計中比較難以掌握的技術(shù)，其中包含的設(shè)計思想非常巧妙，在數(shù)據(jù)結(jié)構(gòu)的課程中有很多算法都用到了遞歸的方法，比如著名的漢諾塔問題就是一個非常經(jīng)典的例子，還有二叉樹的遍歷、快速排序等等。但是遞歸算法的設(shè)計比較困難，甚至有的問題簡直無法用遞歸去解決，關(guān)鍵在于是否掌握了遞歸算法的核心思想。遞歸算法的核心在于三個方面：首先，合理的分析問題，采用將大問題采用分而治之的思想，就是大規(guī)模的問題合理地分成幾個類型相同的但是規(guī)模稍微小一點兒的問題，直至到達(dá)我們能夠解決的程度；其次，分析如果問題到達(dá)能夠解決的程度后應(yīng)該怎么解決，也就是遞歸該怎么返回的問題；最后，參數(shù)的傳遞，當(dāng)前的狀態(tài)是否需要保存到下一層遞歸，如果需要，該如何傳遞。如果能夠解決好這樣三個問題，就是把握好了設(shè)計遞歸算法的關(guān)鍵點，設(shè)計就有章可循。下面通過兩個例子說明設(shè)計遞歸算法的三個關(guān)鍵點。

2 劃分問題

合理的劃分問題是在程序設(shè)計中應(yīng)用遞歸算法的第一步，如果不能做好這一步工作，其余都免談。有的問題劃分比較容易，可以看到非常清晰的劃分方法，比如漢諾塔，在分析過程中可以非常清晰的看到大問題一步步分解成小問題的過程。但是有的問題就比較麻煩，這個過程并不清晰。比如這樣一個例子：使用遞歸算法實現(xiàn)不帶表頭結(jié)點單鏈表的逆序。首先看一下不帶表頭結(jié)點單鏈表逆序的非遞歸實現(xiàn)方法，逆序的過程如圖1所示，其中L表示指向單鏈表第一個結(jié)點的指針，p和q表示在逆序過程中用的臨時指針變量。

其中結(jié)點定義如下：

typedef struct Node{

datatype data;

struct Node *next;

} Node， *Linklist;

逆序的代碼如下：

void reverse(Linklist *L){

if(!(*L) || !(*L)->next)// 如果是空鏈表或者只有一個結(jié)點的單鏈表，直接返回

return;

Linklist p， q;

p = (*L)->next;

while(p){

q = p->next;

p->next = *L;

*L = p;

p = q;

} }

通過整個求解過程可以發(fā)現(xiàn)，算法并不復(fù)雜，但如果要用遞歸不好下手，看不見清晰的可以把大的問題劃分成小問題的方法。下面我們換一個思路想一想。把整個鏈表分為兩個部分：第一個結(jié)點和其余所有結(jié)點組成的單鏈表（假設(shè)為L1），所謂逆序就是如下的過程：

1) 把L1逆序

2) 第一個結(jié)點放在逆序后的L1的最后一個結(jié)點的后面

3) 使用同樣的方法對L1逆序

這就是一個遞歸的過程。同樣設(shè)函數(shù)名為reverse(Linklise L)，算法描述如下：

輸入：待逆序鏈表的第一個結(jié)點

輸出：逆序后鏈表的最后一個結(jié)點

Begin

p := L;

q := L->next;

q := reverse(q)

q->next := p;

p->next := 0;

End

reverse方法返回鏈表逆序后的最后一個結(jié)點。問題劃分清楚后，那么現(xiàn)在進(jìn)入遞歸算法設(shè)計的第二步：什么時候返回?

3 遞歸的返回

遞歸一定要有返回，否則就是無窮遞歸。那遞歸該什么時候返回呢？當(dāng)問題細(xì)分到可以解決的程度時，遞歸就可以返回了，對于我們這個問題，規(guī)模有多大的時候可以解決呢？答案很明確，就是當(dāng)L1中只有一個結(jié)點的時候，逆序不用做任何事情，而且逆序后的最后一個結(jié)點就是這唯一的一個結(jié)點。代碼大致如下：

if(!L || !L->next)// 如果是空鏈表或者只有一個結(jié)點的單鏈表，直接返回該結(jié)點

return L;

下面是完整的代碼：

Linklist LL;

Linklist reverse(Linklist L){

Linklist p， q;

if(!L || !L->next){// 如果是空鏈表或者只有一個結(jié)點的單鏈表，直接返回該結(jié)點

LL = L;// LL為全局變量

return L;

}

p = L;

q = L->next;

q = reverse(q);

q->next = p;

p->next = 0;

return p;

}

由于在遞歸的最后一層返回時，返回的是逆序后的鏈表的最后一個結(jié)點的指針，鏈表的第一個結(jié)點丟失，所以在實現(xiàn)過程中用了一個全局變量LL，用于取得鏈表逆序后的第一個結(jié)點，也就是最深層遞歸函數(shù)返回的結(jié)點。

4 參數(shù)的傳遞

在遞歸的運(yùn)行過程中，當(dāng)由當(dāng)前層進(jìn)入更深層的函數(shù)調(diào)用時，需要保存當(dāng)前的狀態(tài)，也就是將當(dāng)前所使用的資源入棧[1]。臨時變量入棧不需要我們做什么工作，但如果使用了外部資源，并且外部資源的狀態(tài)會影響程序的運(yùn)行時，就必須要在遞歸函數(shù)中做外部資源復(fù)制與傳遞的工作。下面是一個例子：dreamzk 種了3種花 A、B、C 各 a、b、c 盆，每天他都會把這些花搬到外面給他們曬曬太陽，但是他想把這些花擺放得有特色點，于是要求任意相鄰的兩盆花不能相同，一共有多少中擺放方式呢？請你幫他算算。

4.1 問題分析

這個問題可以采用典型的“分而治之”的思想，第一盆花有三種擺放方式：1) 第一盆是A；2) 第一盆是B；3.第一盆是C，分別用RankA、RankB、RankC代表每一種情況的擺放方式的總數(shù)，那么總的排放方式為：RankA+RankB+RankC，這樣就把總問題分解成為三個小問題。現(xiàn)在的問題是：RankA、RankB、RankC是多少？這三者的求解具有相似性，只需要分析一個即可，下面以RankA為例進(jìn)行分析。RankA表示第一盆選擇的是A的情況下一共有多少種擺放方式，第一盆既然已經(jīng)固定了，那么現(xiàn)在的問題成了：一共有三種花A、B、C 各 a-1、b、c 盆，第一盆只能放B或C，一共有多少種擺放方式。繼續(xù)用RankB、RankC代表兩種情況擺放方式的總數(shù)，則可以得到總的擺放數(shù)量是RankB+RankC，只是問題規(guī)模縮小了，然后繼續(xù)可以分解縮小了規(guī)模的RankB和RankC，直至可以解決問題。但是還有兩個問題：

1) 如果某一種花擺放完畢只剩下兩種花怎么辦？那只能兩種花交替放；

2) 如果只剩下了一種花怎么辦？如果剩下的一種花的數(shù)量大于了1，則這種擺放方式不成功，返回0，如果等于1，并且與前一種花不一樣，說明這是一次成功的擺放，返回1；

4.2 準(zhǔn)備

在編程實現(xiàn)之前需要將問題域用計算機(jī)可以處理的方式描述出來，這里的問題是，怎樣描述花的種類和數(shù)量，可以采用一個長度為4的一維數(shù)組，第0位空著，第一位中存儲的數(shù)字代表第一種花的數(shù)量，依次類推。數(shù)組中的內(nèi)容代表每一次遞歸調(diào)用時的狀態(tài)，也就是每一種花有多少，所以每一次遞歸調(diào)用的數(shù)組必須入棧，但是數(shù)組作為參數(shù)時傳遞的是指針，而不是復(fù)制數(shù)組然后傳遞副本，所以這個工作需要編程實現(xiàn)，代碼如下：其中a代表源數(shù)組，b代表目標(biāo)數(shù)組。

void copy_arr(int a[4]， int b[4]){

for(int i = 1; i < 4; i++){

b[i] = a[i];

} }

4.3 實現(xiàn)

根據(jù)前面的分析可以得到，問題一共有三種狀態(tài)：1) 有三種花可以擺放；2) 只有兩種花可以擺放；3) 只剩下一種花擺放。并且當(dāng)前擺放的選擇受到前一盆花的限制，下面一一分析。對于第一種情況，假設(shè)前一盆花擺放的是A，算法如下：

輸入：（1）前一盆花的種類（2）剩下兩盆花的種類（3）當(dāng)前各種花的數(shù)量

輸出：當(dāng)前狀態(tài)下符合題目要求的擺放方式的數(shù)量

步驟1. A種花的數(shù)量減一。

步驟2. 當(dāng)前只能擺放B或者C，如果B的數(shù)量為0（已經(jīng)擺放完了），則當(dāng)前只能擺放C，如果C的數(shù)量為0，則當(dāng)前只能擺放B，在這兩種情況下問題都退化成為第二種狀態(tài)，也就是兩種花的擺放。

步驟3. 否則（也就是B和C都不為0），那么總的可以擺放的方式就是當(dāng)前擺放B和C兩種方式的和，也就是問題分解為規(guī)模小一些的兩個同類問題

具體代碼如下，其中pre表示前一種花的序號，x和y分別表示可以擺放的另外兩種花的序號，flowers表示現(xiàn)有三種花的數(shù)量數(shù)組。

int rank_three(int pre， int x， int y， int flowers[4]){

int new_arr[4];

copy_arr(flowers， new_arr);

new_arr[pre]--;

if(new_arr[x] == 0)

return rank_two(y， pre， new_arr);

else if(new_arr[y] == 0)

return rank_two(x， pre， new_arr);

return rank_three(x， pre， y， new_arr) + rank_three(y， x， pre， new_arr);

}

對于第二種情況，假設(shè)只剩下A和B兩種花，并且前一盆花擺放的是A，算法如下：

輸入：（1）前一盆花的種類（2）剩下一盆花的種類（3）當(dāng)前各種花的數(shù)量

輸出：當(dāng)前狀態(tài)下符合題目要求的擺放方式的數(shù)量

步驟1. A種花的數(shù)量減一。

步驟2. 當(dāng)前只能擺放B，如果B的數(shù)量為0（已經(jīng)擺放完了），則問題退化成為第一種狀態(tài)，也就是一種花的擺放。

步驟3. 否則（也就是B不為0），那么當(dāng)前位置擺放B，問題轉(zhuǎn)變成為規(guī)模小一些的同類問題。

具體代碼如下，其中pre表示前一種花的序號，pos表示可以擺放的另外一種花的序號，flowers表示現(xiàn)有三種花的數(shù)量數(shù)組。

int rank_two(int pre， int pos， int flowers[4]){

int new_arr[4];

copy_arr(flowers， new_arr);

new_arr[pre]--;

if(new_arr[pos] == 0)

return rank_one(pre， new_arr);

return rank_two(pos， pre， new_arr);

}

對于第三種情況，假設(shè)前一盆花是A，那么現(xiàn)在也只能擺放A，因為另外兩種花都擺放完了，所以算法如下：

輸入：（1）前一盆花的種類（2）當(dāng)前各種花的數(shù)量

輸出：當(dāng)前狀態(tài)下符合題目要求的擺放方式的數(shù)量

步驟1. 如果A的數(shù)量不為0，前一盆是A，現(xiàn)在也只能擺放A，說明已經(jīng)無法完成題目的要求，這種擺放方式不符合題目要求，返回0。

步驟2. 否則，如果A的數(shù)量為0，說明所有的花都按照要求擺放完畢，這是一次合乎要求的擺放，返回1。

具體代碼如下，其中pos表示需要擺放的花的序號，flowers表示現(xiàn)有三種花的數(shù)量數(shù)組。

int rank_one(int pos， int flowers[4]){

if(flowers[pos] == 0)

return 1;

return 0;

}

總的問題分解為三個第一類問題，就是第一個擺放A、B、C，總的擺放方式為三者之和，代碼如下，其中flowers表示初始狀態(tài)三種花的數(shù)量數(shù)組。

int rank(int flowers[4]){

return rank_three(1， 2， 3， flowers) + rank_three(2， 1， 3， flowers) + rank_three(3， 1， 2， flowers);

}

至此，通過將大問題不斷細(xì)分成若干小問題，運(yùn)用遞歸方法解決了看似很復(fù)雜的問題，在這個題目當(dāng)中，多次用到了拷貝數(shù)組的過程，這是由于數(shù)組當(dāng)作參數(shù)傳遞時，傳遞的是指針，并沒有做數(shù)組的復(fù)制，在這個題目當(dāng)中每一次遞歸的調(diào)用都必須擁有一份獨立的當(dāng)前各種花的數(shù)量數(shù)組的拷貝，所以在每一次修改花的數(shù)量之前都要做數(shù)組的拷貝工作。做好參數(shù)的傳遞，這是在設(shè)計遞歸算法時需要考慮的重要步驟之一。

5 結(jié)束語

使用遞歸算法可以解決一些看起來非常復(fù)雜、無從下手的問題，雖然參考文獻(xiàn)[3]和[4]提及了遞歸算法的時間和空間效率問題，提出了遞歸算法的非遞歸解決方案，但是隨著計算機(jī)硬件的發(fā)展，在很多軟件開發(fā)過程中并不在乎那一點點效率損失，而編程的簡潔性成為更重要的一個方面[2]，此時是遞歸算法一展身手的機(jī)會，好的遞歸算法設(shè)計非常精巧，可以用很少的代碼解決復(fù)雜的問題，遞歸算法的設(shè)計通常比較困難，但也是有章可循，通過把握住設(shè)計過程的三個關(guān)鍵問題，能夠使這一強(qiáng)大工具在程序設(shè)計中更好的發(fā)揮作用。本文創(chuàng)新點在于對遞歸算法設(shè)計的關(guān)鍵技術(shù)進(jìn)行了總結(jié)，并通過示例加以說明。

參考文獻(xiàn)：

[1] 岳愛菊，杜海濤.淺析遞歸和遞推[J].山東電大學(xué)報，2005(4):27-28.

[2] 劉萍，黃小蘭.例析程序設(shè)計中的遞歸算法[J].青海師專學(xué)報，2007(5):118-121.

[3] 王晅，郭芳俠，王振邦.遞歸問題的非遞歸算法及效率分析[J].陜西師范大學(xué)學(xué)報學(xué)報，2005，1(33):63-65.

[4] 陳燕暉，邢晶，羅宇.一種消除遞歸的新方法[J].計算機(jī)工程與應(yīng)用，2006(4):73-75.

[5] 王曉劍，王安民，孟憲君，等.遞歸在故障診斷專家系統(tǒng)設(shè)計中的應(yīng)用[J].微計算機(jī)信息，2008，1-1:154-156.