1第6章遞歸算法遞歸的概念遞歸算法的執(zhí)行過程遞歸算法的設(shè)計方法遞歸過程和運行時棧遞歸算法的效率分析設(shè)計舉例主要知識點2存在算法調(diào)用自己的情況：

若一個算法直接的或間接的調(diào)用自己本身，則稱這個算法是遞歸算法。（1）問題的定義是遞推的階乘函數(shù)的常見定義是：6.1遞歸的概念3也可定義為：寫成函數(shù)形式，則為：

這種函數(shù)定義的方法是用階乘函數(shù)自己本身定義了階乘函數(shù)，稱公式（6–3）是階乘函數(shù)的遞推定義式。4（2）問題的解法存在自調(diào)用

一個典型的例子是在有序數(shù)組中查找一個數(shù)據(jù)元素是否存在的折半查找算法。

56

6.2遞歸算法的執(zhí)行過程

例6-1給出按照公式6-3計算階乘函數(shù)的遞歸算法，并給出n=3時遞歸算法的執(zhí)行過程。設(shè)計：按照公式6-3計算階乘函數(shù)的遞歸算法如下：7longintFact(intn){intx;longinty; if(n<0)//n<0時階乘無定義

{printf(“參數(shù)錯！”); return-1; }

if(n==0)return1;else

{y=Fact(n-1); //遞歸調(diào)用

returnn*y;}}8設(shè)計主函數(shù)如下voidmain(void){longintfn;

fn=Fact(3);}主函數(shù)用實參n=3調(diào)用了遞歸算法Fact(3)，而Fact(3)要通過調(diào)用Fact(2)、Fact(2)要通過調(diào)用Fact(1)、Fact(1)要通過調(diào)用Fact(0)來得出計算結(jié)果。Fact(3)的遞歸調(diào)用過程如圖6-2所示。9圖6-2Fact(3)的遞歸調(diào)用執(zhí)行過程10

例6-2給出在有序數(shù)組a中查找數(shù)據(jù)元素x是否存在的遞歸算法，并給出如圖6-1所示實際數(shù)據(jù)的遞歸算法的執(zhí)行過程。遞歸算法如下：11intBSearch(inta[],intx,intlow,inthigh){ intmid;

if(low>high)return-1;

//查找不成功

mid=(low+high)/2;

if(x==a[mid]) returnmid; //查找成功

elseif(x<a[mid])

returnBSearch(a,x,low,mid-1); //在下半?yún)^(qū)查找

else

returnBSearch(a,x,mid+1,high); //在上半?yún)^(qū)查找}12測試主函數(shù)設(shè)計如下：#include<stdio.h>

main(void){inta[]={1,3,4,5,17,18,31,33}; intx=17;intbn;

bn=BSearch(a,x,0,7);if(bn==-1)printf("x不在數(shù)組a中");elseprintf("x在數(shù)組a的下標%d中",bn);}13

BSearch(a,x,0,7)的遞歸調(diào)用過程如圖6-3所示，其中，實箭頭表示函數(shù)調(diào)用，虛箭頭表示函數(shù)的返回值。

圖6-3BSearch(a,x,0,7)的遞歸調(diào)用過程14156.3遞歸算法的設(shè)計方法遞歸算法既是一種有效的算法設(shè)計方法，也是一種有效的分析問題的方法。遞歸算法求解問題的基本思想是：對于一個較為復(fù)雜的問題，把原問題分解成若干個相對簡單且類同的子問題,這樣，原問題就可遞推得到解。16適宜于用遞歸算法求解的問題的充分必要條件是：（1）問題具有某種可借用的類同自身的子問題描述的性質(zhì)；（2）某一有限步的子問題（也稱作本原問題）有直接的解存在。

當(dāng)一個問題存在上述兩個基本要素時，該問題的遞歸算法的設(shè)計方法是：（1）把對原問題的求解設(shè)計成包含有對子問題求解的形式。（2）設(shè)計遞歸出口。17例6-3設(shè)計模擬漢諾塔問題求解過程的算法。漢諾塔問題的描述是：設(shè)有3根標號為A，B，C的柱子，在A柱上放著n個盤子，每一個都比下面的略小一點，要求把A柱上的盤子全部移到C柱上，移動的規(guī)則是：（1）一次只能移動一個盤子；（2）移動過程中大盤子不能放在小盤子上面；（3）在移動過程中盤子可以放在A，B，C的任意一個柱子上。18問題分析：

可以用遞歸方法求解n個盤子的漢諾塔問題。基本思想：

1個盤子的漢諾塔問題可直接移動。n個盤子的漢諾塔問題可遞歸表示為，首先把上邊的n-1個盤子從A柱移到B柱，然后把最下邊的一個盤子從A柱移到C柱，最后把移到B柱的n-1個盤子再移到C柱。4個盤子漢諾塔問題的遞歸求解示意圖如圖6-4所示。

19圖6-4漢諾塔問題的遞歸求解示意圖

20算法設(shè)計：首先，盤子的個數(shù)n是必須的一個輸入?yún)?shù)，對n個盤子,我們可從上至下依次編號為1,2,…,n；其次，輸入?yún)?shù)還需有3個柱子的代號,我們令3個柱子的參數(shù)名分別為fromPeg，auxPeg和toPeg；最后，漢諾塔問題的求解是一個處理過程，因此算法的輸出是n個盤子從柱子fromPeg借助柱子auxPeg移動到柱子toPeg的移動步驟，我們設(shè)計每一步的移動為屏幕顯示如下形式的信息：

MoveDiskifromPegXtoPegY

這樣，漢諾塔問題的遞歸算法可設(shè)計如下：

21voidtowers(intn,charfromPeg,chartoPeg,charauxPeg){if(n==1) //遞歸出口

{printf("%s%c%s%c\n","movedisk1frompeg", fromPeg,"topeg",toPeg); return;}

//把n-1個圓盤從fromPeg借助toPeg移至auxPegtowers(n-1,fromPeg,auxPeg,toPeg);

//把圓盤n由fromPeg直接移至toPegprintf("%s%d%s%c%s%c\n","movedisk",n,"frompeg",fromPeg,"topeg",toPeg);

//把n-1個圓盤從auxPeg借助fromPeg移至toPegtowers(n-1,auxPeg,toPeg,fromPeg);}22測試主函數(shù)如下：#include<stdio.h>

voidmain(void){ Towers(4,'A','C','B');}程序運行的輸出信息如下：23MoveDisk1fromPegAtoPegBMoveDisk2fromPegAtoPegCMoveDisk1fromPegBtoPegCMoveDisk3fromPegAtoPegBMoveDisk1fromPegCtoPegAMoveDisk2fromPegCtoPegBMoveDisk1fromPegAtoPegBMoveDisk4fromPegAtoPegCMoveDisk1fromPegBtoPegCMoveDisk2fromPegBtoPegAMoveDisk1fromPegCtoPegAMoveDisk3fromPegBtoPegCMoveDisk1fromPegAtoPegBMoveDisk2fromPegAtoPegCMoveDisk1fromPegBtoPegC24總結(jié)如下：遞歸算法的執(zhí)行過程是不斷地自調(diào)用，直到到達遞歸出口才結(jié)束自調(diào)用過程；到達遞歸出口后，遞歸算法開始按最后調(diào)用的過程最先返回的次序返回；返回到最外層的調(diào)用語句時遞歸算法執(zhí)行過程結(jié)束。

256.4遞歸過程和運行時棧對于非遞歸函數(shù)，調(diào)用函數(shù)在調(diào)用被調(diào)用函數(shù)前，系統(tǒng)要保存以下兩類信息：（1）調(diào)用函數(shù)的返回地址；（2）調(diào)用函數(shù)的局部變量值。當(dāng)執(zhí)行完被調(diào)用函數(shù)，返回調(diào)用函數(shù)前，系統(tǒng)首先要恢復(fù)調(diào)用函數(shù)的局部變量值，然后返回調(diào)用函數(shù)的返回地址。

26遞歸函數(shù)被調(diào)用時，系統(tǒng)要作的工作和非遞歸函數(shù)被調(diào)用時系統(tǒng)要作的工作在形式上類同，但保存信息的方法不同。遞歸函數(shù)被調(diào)用時，系統(tǒng)需要一個運行時棧（這是一個堆棧）。系統(tǒng)的運行時棧也要保存上述兩類信息。每一層遞歸調(diào)用所需保存的信息構(gòu)成運行時棧的一個工作記錄，在每進入下一層遞歸調(diào)用時，系統(tǒng)就建立一個新的工作記錄，并把這個工作記錄進棧成為運行時棧新的棧頂；每返回一層遞歸調(diào)用，就退棧一個工作記錄。因為棧頂?shù)墓ぷ饔涗洷囟ㄊ钱?dāng)前正在運行的遞歸函數(shù)的工作記錄，所以棧頂?shù)墓ぷ饔涗浺卜Q為活動記錄。276.5遞歸算法的效率分析斐波那契數(shù)列Fib(n)的遞推定義是：

求第n項斐波那契數(shù)列的遞歸函數(shù)如下：

longFib(intn){if(n==0||n==1)returnn;//遞歸出口

elsereturnFib(n-1)+Fib(n-2);//遞歸調(diào)用}28

用歸納法可以證明求Fib(n)的遞歸調(diào)用次數(shù)等于2n-1；計算斐波那契數(shù)列的遞歸函數(shù)Fib(n)的時間復(fù)雜度為O(2n)。計算斐波那契數(shù)列Fib(n)問題，我們也可根據(jù)公式寫出循環(huán)方式求解的函數(shù)如下：

圖6-6Fib(5)的遞歸調(diào)用樹29longFib2(intn){longintoneBack,twoBack,current;inti;

if(n==0||n==1)returnn;else{oneBack=1; twoBack=0; for(i=2;i<=n;i++) {current=oneBack+twoBack; twoBack=oneBack; oneBack=current; } returncurrent; }}30

上述循環(huán)方式的計算斐波那契數(shù)列的函數(shù)Fib2(n)的時間復(fù)雜度為O(n)。對比循環(huán)結(jié)構(gòu)的Fib2(n)和遞歸結(jié)構(gòu)的Fib(n)可發(fā)現(xiàn)，循環(huán)結(jié)構(gòu)的Fib2(n)算法在計算第n項的斐波那契數(shù)列時保存了當(dāng)前已經(jīng)計算得到的第n-1項和第n-2項的斐波那契數(shù)列，因此其時間復(fù)雜度為O(n)；而遞歸結(jié)構(gòu)的Fib(n)算法在計算第n項的斐波那契數(shù)列時，必須首先計算第n-1項和第n-2項的斐波那契數(shù)列，而某次遞歸計算得出的斐波那契數(shù)列，如Fib(n-1)、Fib(n-2)等無法保存，下一次要用到時還需要重新遞歸計算，因此其時間復(fù)雜度為O(2n)

。

316.6設(shè)計舉例6.6.1一般遞歸算法設(shè)計舉例

例6-6設(shè)計一個輸出如下形式數(shù)值的遞歸算法。

nnn...n ...... 333 22 132問題分析：該問題可以看成由兩部分組成：一部分是輸出一行值為n的數(shù)值；另一部分是原問題的子問題，其參數(shù)為n-1。當(dāng)參數(shù)減到0時不再輸出任何數(shù)據(jù)值，因此遞歸的出口是當(dāng)參數(shù)n≤0時空語句返回。

算法設(shè)計：遞歸算法設(shè)計如下：

voidDisplay(intn){inti;

for(i=1;i<=n;i++) cout<<setw(s)<<n; cout<<endl;

if(n>0)Display(n-1);

//遞歸

//n<=0為遞歸出口，遞歸出口為空語句

}33

例6-7設(shè)計求解委員會問題的算法。委員會問題是：從一個有n個人的團體中抽出k(k≤n)個人組成一個委員會，計算共有多少種構(gòu)成方法。

問題分析：從n個人中抽出k(k≤n)個人的問題是一個組合問題。把n個人固定位置后，從n個人中抽出k個人的問題可分解為兩部分之和：第一部分是第一個人包括在k個人中，第二部分是第一個人不包括在k個人中。對于第一部分，則問題簡化為從n-1個人中抽出k-1個人的問題；對于第二部分，則問題簡化為從n-1個人中抽出k個人的問題。圖6-7給出了n=5,k=2時問題的分解示意圖。34圖6-7委員會問題分解示意圖35

當(dāng)n=k或k=0時，該問題可直接求解，數(shù)值均為1，這是算法的遞歸出口。因此，委員會問題的遞推定義式為：36intComm(intn,intk){if(n<1||k<0||k>n)return0;

if(k==0)return1; if(n==k)return1; returnComm(n-1,k-1)+Comm(n-1,k);}37補充例子。

求兩個正整數(shù)n和m最大公約數(shù)的遞推定義式為：要求：

（1）編寫求解該問題的遞歸算法；（2）分析當(dāng)調(diào)用語句為Gcd(30,4)時算法的執(zhí)行過程和執(zhí)行結(jié)果；（3）分析當(dāng)調(diào)用語句為Gcd(97,5)時算法的執(zhí)行過程和執(zhí)行結(jié)果；（4）編寫求解該問題的循環(huán)結(jié)構(gòu)算法。38解：（1）遞歸算法如下：

intGcd(intn,intm){if(n<0||m<0)exit(0);if(m==0)returnn;elseif(m>n)returnGcd(m,n);elsereturnGcd(m,n%m);}

39

（2）調(diào)用語句為Gcd(30,4)時，因m<n，遞歸調(diào)用Gcd(4,2)；因m<n，遞歸調(diào)用Gcd(2,0)；因m=0，到達遞歸出口，函數(shù)最終返回值為n=2，即30和4的最大公約數(shù)為2。（3）調(diào)用語句為Gcd(5,97)時，因m>n，遞歸調(diào)用Gcd(97,5)；因m<n，遞歸調(diào)用Gcd(5,2)；因m<n，遞歸調(diào)用Gcd(2,1)；因m<n，遞歸調(diào)用Gcd(1,0)；因m=0，到達遞歸出口，函數(shù)最終返回值為n=1，即5和9