數(shù)據(jù)結(jié)構(gòu)第5章-遞歸

數(shù)據(jù)結(jié)構(gòu)李云清楊慶紅揭安全人民郵電出版社高等學(xué)校精品課程（省級）國家十二五規(guī)劃教材高等學(xué)校精品課程（省級）國家十二五規(guī)劃教材揭安全jieanquan@163.com江西師范大學(xué)計(jì)算機(jī)信息工程學(xué)院第5章遞歸第5章遞歸遞歸與遞歸程序設(shè)計(jì)遞歸程序到非遞歸程序的轉(zhuǎn)換遞歸程序設(shè)計(jì)的應(yīng)用實(shí)例遞歸程序執(zhí)行過程的分析

在一個(gè)函數(shù)的定義中出現(xiàn)了對自己本身的調(diào)用，稱之為直接遞歸；或者一個(gè)函數(shù)p的定義中包含了對函數(shù)q的調(diào)用，而q的實(shí)現(xiàn)過程又調(diào)用了p，即函數(shù)調(diào)用形成了一個(gè)環(huán)狀調(diào)用鏈,這種方式稱之為間接遞歸。遞歸技術(shù)在算法和程序設(shè)計(jì)中是一種十分有用的技術(shù)，許多高級程序設(shè)計(jì)語言均提供了支持遞歸定義的機(jī)制和手段。

5.1遞歸與遞歸程序設(shè)計(jì)

例1

試編一個(gè)遞歸函數(shù)，求正整數(shù)n的階乘值n！。

用fact(n)表示n的階乘值，據(jù)階乘的數(shù)學(xué)定義可知：

1n=0

fact(n)=

n*fact(n-1)n>0

5.1遞歸與遞歸程序設(shè)計(jì)該問題的算法為：intFact(intn)

{intm;

if(n==0)return(1);

else

{m=n*Fact(n-1);

return(m);}

}

例2

試編一個(gè)遞歸函數(shù)，求第n項(xiàng)Fibonacci級數(shù)的值。

假設(shè)使用Fibona(n)表示第n項(xiàng)Fibonacci級數(shù)的值，

根據(jù)Fibonacci級數(shù)的計(jì)算公式：

1 n=1

Fibona(n)=1 n=2

Fibona(n-1)+Fibona(n-2)n>2該問題的算法為：

intFibona(intn)

{intm;

if(n==1)return(1);

elseif(n==2)return(1);

else

{m=Fibona(n-1)+Fibona(n-2);

return(m);

}

}

遞歸程序設(shè)計(jì)具有以下兩個(gè)特點(diǎn)：（1）具備遞歸出口。遞歸出口定義了遞歸的終止條件，當(dāng)程序的執(zhí)行使它得到滿足時(shí)，遞歸執(zhí)行過程便終止。有些問題的遞歸程序可能存在幾個(gè)遞歸出口；（2）在不滿足遞歸出口的情況下，根據(jù)所求解問題的性質(zhì)，將原問題分解成若干子問題，這些子問題的結(jié)構(gòu)與原問題的結(jié)構(gòu)相同，但規(guī)模較原問題小。子問題的求解通過以一定的方式修改參數(shù)進(jìn)行函數(shù)自身調(diào)用加以實(shí)現(xiàn)，然后將子問題的解組合成原問題的解。遞歸調(diào)用時(shí)，參數(shù)的修改最終必須保證遞歸出口得以滿足。

在遞歸程序的運(yùn)行過程中，系統(tǒng)內(nèi)部設(shè)立了一個(gè)棧，用于存放每次函數(shù)調(diào)用與返回所需的各種數(shù)據(jù)，主要包括：函數(shù)調(diào)用執(zhí)行完成時(shí)的返回地址、函數(shù)的返回值、每次函數(shù)調(diào)用的實(shí)在參數(shù)和局部變量。

在遞歸程序的執(zhí)行過程中，每當(dāng)執(zhí)行函數(shù)調(diào)用時(shí)，必須完成以下任務(wù)：

（1）計(jì)算當(dāng)前被調(diào)用函數(shù)每個(gè)實(shí)在參數(shù)的值；

（2）為當(dāng)前被調(diào)用的函數(shù)分配一片存儲空間，用于存放其所需的各種數(shù)據(jù)，并將這片存儲空間的首地址壓入棧中；

（3）將當(dāng)前被調(diào)用函數(shù)的實(shí)在參數(shù)、將來當(dāng)前函數(shù)執(zhí)行完畢后的返回地址等數(shù)據(jù)存入上述所分配的存儲空間中；

（4）控制轉(zhuǎn)到被調(diào)用函數(shù)的函數(shù)體，從其第一個(gè)可執(zhí)行的語句開始執(zhí)行。

5．2遞歸程序執(zhí)行過程的分析

當(dāng)從被調(diào)用的函數(shù)返回時(shí)，必須完成以下任務(wù)：

（1）如果被調(diào)用的函數(shù)有返回值，則記下該返回值，同時(shí)通過棧頂元素到該被調(diào)用函數(shù)對應(yīng)的存儲空間中取出其返回地址；

（2）把分配給被調(diào)用函數(shù)的那片存儲空間回收，棧頂元素出棧；

（3）按照被調(diào)用函數(shù)的返回地址返回到調(diào)用點(diǎn)，若有返回值，還必須將返回值傳遞給調(diào)用者，并繼續(xù)程序的執(zhí)行。

例3

試編寫一個(gè)遞歸函數(shù)，在第一行打印輸出1個(gè)1，在第二行打印輸出2個(gè)2，……在第n行打印輸出n個(gè)n。例如，當(dāng)n=5時(shí)，調(diào)用該函數(shù)的輸出結(jié)果為：

1

22

333

4444

55555

該問題的算法為:print(intn)

{inti;

if(n!=0)

{print(n-1);for(i=1;i<=n;i++)

printf("%d",n);printf("\n");}

}print(5)print(4)for(i=1;i<=5;i++)printf(“%d”,5)printf(“\n”);print(3)for(i=1;i<=4;i++)printf(“%d”,4)printf(“\n”);5!=0結(jié)束print(2)for(i=1;i<=3;i++)printf(“%d”,3)printf(“\n”);遞歸print(1)for(i=1;i<=2;i++)printf(“%d”,2)printf(“\n”);print(0)for(i=1;i<=1;i++)printf(“%d”,1)printf(“\n”);分析Fibona(5)S0(1)m=Fibona(4)+Fibona(3);return(m);m=Fibona(3)+Fibona(2);return(m);(2)m=Fibona(2)+Fibona(1);return(m);(3)m=Fibona(2)+Fibona(1);

return(m);1return(1)(4)return(1)(5)return(1)(6)(7)(8)(9)return(1)return(1)(10)Fibona(5)的執(zhí)行過程S1S2S311123(11)(12)(13)(14)1(15)(17)(18)52例4:課堂舉例:1、遞歸找數(shù)組中的最大數(shù)2、遞歸倒置數(shù)組3、遞歸二分查找4、遞歸倒序遍歷帶頭結(jié)點(diǎn)的單鏈表5、全排列問題例5：下面程序的輸出結(jié)果：voidprintd(intn){if(n<0){putchar('-');n=-n;}if(n/10)printd(n/10);putchar(n%10+'0');}voidmain(){printd(-1234);}排列問題設(shè)計(jì)一個(gè)遞歸算法生成n個(gè)元素{r1,r2,…,rn}的全排列。設(shè)R={r1,r2,…,rn}是要進(jìn)行排列的n個(gè)元素，Ri=R-{ri}。集合X中元素的全排列記為perm(X)。(ri)perm(X)表示在全排列perm(X)的每一個(gè)排列前加上前綴得到的排列。R的全排列可歸納定義如下：當(dāng)n=1時(shí)，perm(R)=(r)，其中r是集合R中唯一的元素；當(dāng)n>1時(shí)，perm(R)由(r1)perm(R1),(r2)perm(R2)，…，(rn)perm(Rn)構(gòu)成。按照上面給出的遞歸定義，可設(shè)計(jì)產(chǎn)生Perm（R）的遞歸算法：

算法Perm(list,k,n)遞歸地產(chǎn)生所有前綴是list[0:k-1]，且后綴是list[k:n]的全排列的所有排列。調(diào)用Perm(list,0,n-1)則產(chǎn)生list[0:n-1]的全排列。

一般情況下執(zhí)行else分支，將list[k:n]中的每一個(gè)元素分別與list[k]中元素交換，然后遞歸的計(jì)算list[k+1:n]的全排列，并將計(jì)算結(jié)果作為list[0:k]的后綴。voidperm(intlist[],intk,intn){inti,temp;if(k==n-1)print(list,n);else{for(i=k;i<n;i++) {temp=list[k];list[k]=list[i]; list[i]=temp;perm(list,k+1,n);temp=list[i];list[i]=list[k];list[k]=temp;}}}#include<stdio.h>intcont=1;/*輸出數(shù)組list的值*/voidprint(intlist[],intn){inti;printf("%2d:",cont++);for(i=0;i<n;i++)printf("%d",list[i]);printf("\n");}/*本函數(shù)判斷整數(shù)序列str[]是否滿足進(jìn)出棧規(guī)則*/voidprint(intstr[],intn){inti,j,k,l,m,flag=1,b[2];for(i=0;i<n;i++) /*對每個(gè)str[i]判斷其后比它小的數(shù)是否為降序序列*/{m=0;for(j=i+1;j<n&&flag;j++)if(str[i]>str[j]){if(m==0)b[m++]=str[j];else{if(str[j]>b[0]){flag=0;} elseb[0]=str[j];}}}if(flag) /*滿足出棧規(guī)則則輸出str[]中的序列*/{ printf("%2d:",cont++); for(i=0;i<n;i++) printf("%d",str[i]); printf("\n");}}intmain(){intstr[100],n,i;printf("inputaint:");/*輸出排列的元素個(gè)數(shù)*/scanf("%d",&n);for(i=0;i<n;i++) /*初始化排列集合*/str[i]=i+1;printf("inputtheresult:\n");perm(str,0,n);printf("\n");return0;}

采用遞歸方式實(shí)現(xiàn)問題的算法程序具有結(jié)構(gòu)清晰、可讀性好、易于理解等優(yōu)點(diǎn)，但遞歸程序較之非遞歸程序無論是空間需求還是時(shí)間需求都更高，因此在希望節(jié)省存儲空間和追求執(zhí)行效率的情況下，人們更希望使用非遞歸方式實(shí)現(xiàn)問題的算法程序；

另外，有些高級程序設(shè)計(jì)語言沒有提供遞歸的機(jī)制和手段，對于某些具有遞歸性質(zhì)的問題（簡稱遞歸問題）無法使用遞歸方式加以解決，必須使用非遞歸方式實(shí)現(xiàn)。因此，本小節(jié)主要研究遞歸程序到非遞歸程序的轉(zhuǎn)換方法。

5.3遞歸程序到非遞歸程序的轉(zhuǎn)換

一般而言，求解遞歸問題有兩種方式：

（1）在求解過程中直接求值，無需回溯。稱這類遞

歸問題為簡單遞歸問題；

（2）另一類遞歸問題在求解過程中不能直接求值，

必須進(jìn)行試探和回溯，稱這類遞歸問題為復(fù)雜

遞歸問題。

兩類遞歸問題在轉(zhuǎn)換成非遞歸方式實(shí)現(xiàn)時(shí)所采用的方法是不同的。通常簡單遞歸問題可以采用遞推方法直接求解；而復(fù)雜遞歸問題由于要進(jìn)行回溯，在實(shí)現(xiàn)過程中必須借助棧來管理和記憶回溯點(diǎn)。

采用遞歸技術(shù)求解問題的算法程序是自頂向下產(chǎn)生計(jì)算序列，其缺點(diǎn)之一是導(dǎo)致程序執(zhí)行過程中許多重復(fù)的函數(shù)調(diào)用。遞推技術(shù)同樣以分劃技術(shù)為基礎(chǔ)，它也要求將需求解的問題分劃成若干與原問題結(jié)構(gòu)相同、但規(guī)模較小的子問題；與遞歸技術(shù)不同的是，遞推方法是采用自底向上的方式產(chǎn)生計(jì)算序列，其首先計(jì)算規(guī)模最小的子問題的解，然后在此基礎(chǔ)上依次計(jì)算規(guī)模較大的子問題的解，直到最后產(chǎn)生原問題的解。由于求解過程中每一步新產(chǎn)生的結(jié)果總是直接以前面已有的計(jì)算結(jié)果為基礎(chǔ)，避免了許多重復(fù)的計(jì)算，因而遞推方法產(chǎn)生的算法程序比遞歸算法具有更高的效率。5.3.1簡單遞歸程序到非遞歸程序的轉(zhuǎn)換簡單遞歸問題非遞歸實(shí)現(xiàn)的基本思想：將原問題分解成若干結(jié)構(gòu)與原問題相同，但規(guī)模較小的子問題，并建立原問題與子問題解之間的遞推關(guān)系，然后定義若干變量用于記錄遞推關(guān)系的每個(gè)子問題的解；程序的執(zhí)行便是根據(jù)遞推關(guān)系，不斷修改這些變量的值，使之成為更大子問題的解的過程；當(dāng)?shù)玫皆瓎栴}解時(shí)，遞推過程便可結(jié)束了。例5

采用非遞歸方式實(shí)現(xiàn)求正整數(shù)n的階乘值。

仍使用Fact(n)表示n的階乘值。要求解Fact(n)的值，可以考慮i從0開始，依次取1,2,……，一直到n，分別求Fact(i)的值，且保證求解Fact(i)時(shí)總是以前面已有的求解結(jié)果為基礎(chǔ)；當(dāng)i=n時(shí)，F(xiàn)act(i)的值即為所求的Fact(n)的值。

根據(jù)階乘的遞歸定義，不失一般性，顯然有以下遞推關(guān)系成立：

1i=0

Fact(i)=

i*Fact(i-1)i>0上述遞推關(guān)系表明Fact(i)是建立于Fact(i-1)的基礎(chǔ)上的，在求解Fact(i)時(shí)子問題只有一個(gè)Fact(i-1)，且整個(gè)Fact(n)的求解過程無需回溯，因此該問題屬于簡單遞歸問題，可以使用遞推技術(shù)加以實(shí)現(xiàn)，實(shí)現(xiàn)過程中只需定義一個(gè)變量fac始終記錄子問題Fact(i-1)的值。初始時(shí)，i=1,fac=Fact(i-1)=Fact(0)=1；在此基礎(chǔ)上根據(jù)以上遞推關(guān)系不斷向前遞推，使i的值加大，直至i=n為止。

階乘問題的非遞歸算法的實(shí)現(xiàn)如下：

intFact(intn)

{

inti,fac;

fac=1;/*將變量fac初始化為Fact(0)的值*/

for(i=1;i<=n;++i)fac=i*fac;

/*根據(jù)遞推關(guān)系進(jìn)行遞推*/

return(fac);

}

【例6】已知有順序表定義如下所示：

#defineMAXSIZE100

typedefintdatatype;

typedefstruct{

datatypea[MAXSIZE];

intsize;

}sequence_list;

請分別使用遞歸與非遞歸方式，實(shí)現(xiàn)順序表中所有元素的逆轉(zhuǎn)。例如，假設(shè)順序表L含有10個(gè)元素，且L.a中所有元素的值為：

562134912332981683

逆轉(zhuǎn)后L.a中所有元素的排列順序?yàn)椋?/p>

831698233129342156voidreverse1(sequence_list*L,intleft,intright){/將順序表L中從下標(biāo)為left的元素開始到下標(biāo)為right的元素構(gòu)成的子數(shù)組段進(jìn)行逆轉(zhuǎn)/datatypetemp;if(left<right){reverse1(L,left+1,right-1);temp=L->a[left];/將下標(biāo)為left的元素和下標(biāo)為right的元素的值進(jìn)行交換/L->a[left]=L->a[right];L->a[right]=temp;}

}voidreverse2(sequence_list*L){/將順序表L中的元素進(jìn)行逆轉(zhuǎn)/datatypetemp;intleft=0,right=L->size-1;while(left<right){temp=L->a[left];/將下標(biāo)為left的元素和下標(biāo)為right的元素的值進(jìn)行交換/L->a[left++]=L->a[right];L->a[right--]=temp;}}

復(fù)雜遞歸問題在求解的過程中無法保證求解動(dòng)作一直向前，往往需要設(shè)置一些回溯點(diǎn)，當(dāng)求解無法進(jìn)行下去或當(dāng)前處理的工作已經(jīng)完成時(shí)，必須退回到所設(shè)置的回溯點(diǎn)，繼續(xù)問題的求解。因此，在使用非遞歸方式實(shí)現(xiàn)一個(gè)復(fù)雜遞歸問題的算法時(shí)，經(jīng)常使用棧來記錄和管理所設(shè)置的回溯點(diǎn)。

5.3.2復(fù)雜遞歸程序到非遞歸程序的轉(zhuǎn)換5.3.2復(fù)雜遞歸程序到非遞歸程序的轉(zhuǎn)換例7

按中點(diǎn)優(yōu)先的順序遍歷線性表問題：已知線性表list以順序存儲方式存儲，要求按以下順序輸出list中所有結(jié)點(diǎn)的值：首先輸出線性表list中點(diǎn)位置上的元素值，然后輸出中點(diǎn)左部所有元素的值，再輸出中點(diǎn)右部所有元素的值；而無論輸出中點(diǎn)左部所有元素的值還是輸出中點(diǎn)右部所有元素的值，也均應(yīng)遵循以上規(guī)律。例如，已知數(shù)組list中元素的值為：

18

3249266103012845

則list中元素按中點(diǎn)優(yōu)先順序遍歷的輸出結(jié)果為：

641832926121030845

試采用遞歸和非遞歸算法實(shí)現(xiàn)該遍歷問題。

Leftmid-1midmid+1right遞歸實(shí)現(xiàn)算法如下：

#defineMAXSIZE20

typedefintlistarr[MAXSIZE];

voidlistorder(listarrlist,intleft,intright)

{/*將數(shù)組段list[left..right]的元素按中點(diǎn)優(yōu)先順序輸出*/

intmid;

if(left<=right)

{mid=(left+right)/2;

printf("%4d",list[mid]);

listorder(list,left,mid-1);

listorder(list,mid+1,right);

}

}

下面考慮該問題的非遞歸實(shí)現(xiàn)：在線性表的遍歷過程中，輸出中點(diǎn)的值后，中點(diǎn)將線性表分成前半部分和后半部分。接下來應(yīng)該考慮前半部分的遍歷，但在進(jìn)入前半部分的遍歷之前，應(yīng)該將后半部分保存起來，以便訪問完前半部分所有元素后，再進(jìn)入后半部分的訪問。

即在此設(shè)置一個(gè)回溯點(diǎn)，該回溯點(diǎn)應(yīng)該進(jìn)棧保存，具體實(shí)現(xiàn)時(shí)，只需將后半部分起點(diǎn)和終點(diǎn)的下標(biāo)進(jìn)棧即可，棧中的每個(gè)元素均代表一個(gè)尚未處理且在等待被訪問的數(shù)組段。對于每一個(gè)當(dāng)前正在處理的數(shù)組（數(shù)組段）均應(yīng)采用以上相同的方式進(jìn)行處理，直到當(dāng)前正在處理的數(shù)組（數(shù)組段）為空，此時(shí)應(yīng)該進(jìn)行回溯，而回溯點(diǎn)恰巧位于棧頂。于是只要取出棧頂元素，將它所確定的數(shù)組段作為下一步即將遍歷的對象，繼續(xù)線性表的遍歷，直到當(dāng)前正在處理的數(shù)組段為空且棧亦為空（表示已無回溯點(diǎn)），算法結(jié)束。

例：123456初始序列如下：254925*1608rightleft21mid例：

123456處理左序列：254925*1608rightleft21例：

123456轉(zhuǎn)入左序列前應(yīng)保存右序列的位置254925*1608rightleft210123top=-1mid例：

123456在對前半部分進(jìn)行遍歷時(shí)，必須將后半部分的起始位與終止位進(jìn)棧。254925*1608rightleft210123top=046mid例：

123456left與right指向前半部分進(jìn)行遍歷。254925*1608rightleft210123top=046例：

123456下一次遍歷后的狀態(tài)為：254925*1608rightleft210123top=04622mid例：

123456從棧中取得回溯位置。254925*1608rightleft210123top=04622例：

12345

6從棧中取得回溯位置：254925*1608rightleft210123top=04622例：

123456再次從list[4..6]處開始遍歷。254925*1608rightleft210123top=-14622#defineMAXSIZE20

typedefintlistarr[MAXSIZE];

voidlistorder(listarrlist,intleft,int

right)

{typedefstruct{

intl;/*存放待處理數(shù)組段的起點(diǎn)下標(biāo)*/

intr;/*存放待處理數(shù)組段的終點(diǎn)下標(biāo)*/

}stacknode;/*棧中每個(gè)元素的類型*/

stacknodestack[MAXSIZE];

inttop,i,j,mid;/*top為棧頂指針*/

if(left<=right)/*數(shù)組段不為空*/

{top=-1;i=left;j=right;

while(i<=j||top!=-1)

{/*當(dāng)前正在處理的數(shù)組段非空或棧非空*/

if(i<=j)

{mid=(i+j)/2;

printf(“%4d”,list[mid]);

++top;stack[top].l=mid+1;

stack[top].r=j;j=mid-1;

}

else

{/*當(dāng)前正在處理的數(shù)組段為空時(shí)進(jìn)行回溯*/

i=stack[top].l;

j=stack[top].r;

--top;

}

}

}

}例5.8

簡單背包問題：設(shè)有m件物品，重量分別為w1,w2,……wm，對于一個(gè)給定的目標(biāo)值s，判斷能否在m件物品中選出若干件物品，使其重量總和為s，并將這些物品裝入背包中。試編寫兩個(gè)函數(shù)，分別采用遞歸和非遞歸方式實(shí)現(xiàn)上述背包問題。由于各物品的重量值和s的值均可是隨機(jī)的，因此，對于一組具體的輸入值，背包問題可能存在解也可能不存在解。首先考慮簡單背包問題的遞歸實(shí)現(xiàn)算法。為了算法實(shí)現(xiàn)方便，我們假設(shè)物品的重量按從小到大的順序存放于數(shù)組w中，并且選擇物品時(shí)總是優(yōu)先考慮重量大的物品.簡單背包問題遞歸算法的基本思想為：首先考慮選擇物品wm的可能性。wm能否被選取決于在w1,w2,……wm-1中能否選出若干件物品，這些物品的重量總和為s-w[m]。若能從w1,w2,……wm-1中選出重量為s-w[m]的若干件物品，則說明wm可被選擇，此時(shí)可以將w[m]的值打印輸出；否則說明應(yīng)該放棄wm的選擇，考慮wm-1被選擇的可能性；而從w1,w2,……wm-1中選出重量為s-w[m]的若干件物品的過程與從w1,w2,……wm中選出重量為s的若干件物品的過程完全相同，只是所處理的對象不同，于是可以通過遞歸調(diào)用加以實(shí)現(xiàn)。在整個(gè)算法的實(shí)現(xiàn)過程中，一旦確定某個(gè)物品被選擇的可能性不存在，則放棄它，下一步將考慮其前一個(gè)物品被選的可能性。不斷重復(fù)以上過程，直到以下三種情況出現(xiàn)：（1）如果當(dāng)前需要選擇的物品重量總和為0，說明搜索已經(jīng)成功，算法結(jié)束；（2）如果當(dāng)前需要選擇的物品重量總和已經(jīng)小于w1，說明搜索失敗，算法結(jié)束；（3）若當(dāng)前被考慮的選擇物品對象為w0（w0不存在），說明搜索失敗，算法結(jié)束。簡單背包問題的遞歸實(shí)現(xiàn)過程見算法5.9。

下面考慮簡單背包問題非遞歸算法的實(shí)現(xiàn)。仍然假設(shè)物品的重量按從小到大的順序存放于數(shù)組w中，并且選擇物品時(shí)總是優(yōu)先考慮重量大的物品。

由于簡單背包問題的求解明顯帶有試探性，因此該問題屬于復(fù)雜遞歸問題，在實(shí)現(xiàn)過程中必須借助于堆棧來記錄回溯點(diǎn)。于是我們定義一個(gè)棧stack，每當(dāng)試著選擇一件物品，就設(shè)置一個(gè)回溯點(diǎn)，將它的重量和編號壓入棧中；而一旦發(fā)現(xiàn)它被選擇的可能性不存在，則將它出棧，同時(shí)通過其編號取它前面的一個(gè)物品作為當(dāng)前考慮的對象；如果求解過程中遇到無法再求解下去需要回溯的情形，但此時(shí)棧已為空，則說明該背包問題無解，算法的執(zhí)行以失敗而告終；若被選擇物品的重量總和恰巧與s的值相等，則求解成功，算法結(jié)束。簡單背包問題的非遞歸實(shí)現(xiàn)過程見算法5.10。例9

設(shè)計(jì)一個(gè)遞歸函數(shù)，將一個(gè)正整數(shù)n轉(zhuǎn)換成字符串。例如，若n=456，則函數(shù)輸出的結(jié)果為“456”。n的位數(shù)不確定，可以為任意位數(shù)的整數(shù)。

voidconvert(intn)

{inti;

charch;

if((i=n/10)!=0)

convert(i);

ch=(n%10)+'0';

putchar(ch);

}

5．4遞歸程序設(shè)計(jì)的應(yīng)用實(shí)例例10

試編寫一個(gè)遞歸函數(shù)，求兩個(gè)正整數(shù)m和n的最大公約數(shù)，其中最大公約數(shù)gcd(m,n)的求解公式為：

gcd(n,m)m<n

gcd(m,n)=mn=0

gcd(n,m%n)其它情形

intgcd(intm,intn)

{intk;

if(n==0)return(m);

elseif(n>m)return(gcd(n,m));

else

{k=m%n;

return(gcd(n,k));}

}

例11

已知帶頭結(jié)點(diǎn)的單鏈表存儲結(jié)構(gòu)定義如下：

typedefintdatatype;/*預(yù)定義的數(shù)據(jù)類型*/

typedefstructnode

{

datatypedata;/*結(jié)點(diǎn)數(shù)據(jù)域*/

structnode*next;

}linknode;

typedeflinknode*linklist;

請編寫遞歸函數(shù)分別順序（從前向后）、倒序（從后向前）輸出單鏈表內(nèi)容。

voidplefttoright(linklisthead){if(head->next){printf("%5d",head->next->data); /*輸出鏈表的第一個(gè)結(jié)點(diǎn)*/plefttoright(head->next); /*遞歸輸出后序結(jié)點(diǎn)*/}}voidprighttoleft(linklisthead){if(head->next){prighttoleft(head->next);

/*遞歸輸出后序結(jié)點(diǎn)*/printf("%5d",head->next->data); /*輸出鏈表的第一個(gè)結(jié)點(diǎn)*/}}習(xí)題55.1試述遞歸程序設(shè)計(jì)的特點(diǎn)。5.2試簡述簡單遞歸程序向非遞歸程序轉(zhuǎn)換的方法。5.3試簡述復(fù)雜遞歸程序向非遞歸程序轉(zhuǎn)換的方法，并說明棧在復(fù)雜遞歸程序轉(zhuǎn)換成非遞歸程序的過程中所起的作用。5.4試給出例題5.1中Fact(5)的執(zhí)行過程分析。5.5已知多項(xiàng)式pn(x)

=

a0

+

a1x

+

a2x2

+

…

+

anxn的系數(shù)按順序存儲在數(shù)組a中，試：（1）編寫一個(gè)遞歸函數(shù)，求n階多項(xiàng)式的值；（2）編寫一個(gè)非遞歸函數(shù)，求n階多項(xiàng)式的值。5.6已知兩個(gè)一維整型數(shù)組a和b，分別采用遞歸和非遞歸方式編寫函數(shù)，求兩個(gè)數(shù)組的內(nèi)積（數(shù)組的內(nèi)積等于兩個(gè)數(shù)組對應(yīng)元素相乘后再相加所得到的結(jié)果）。5.7寫出求Ackerman函數(shù)Ack(m，n)值的遞歸函數(shù)，Ackerman函數(shù)在m

≥

0和n

≥

0時(shí)的定義為：Ack(0，n)=n+1;Ack(m，0)=Ack(m?1，1);Ack(m，n)=Ack(m?1，Ack(m，n?1))n>0且m>05.8已知多項(xiàng)式Fn(x)的定義如下：試寫出計(jì)算Fn(x)值的遞歸函數(shù)。5.9n階Hanoi塔問題：設(shè)有3個(gè)分別命名為X，Y和Z的塔座，在塔座X上從上到下放有n個(gè)直徑各不相同、編號依次為1，2，3，…，n的圓盤（直徑大的圓盤在下，直徑小的圓盤在上），現(xiàn)要求將X塔座上的n個(gè)