數據結構第5章-遞歸

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

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

5.1遞歸與遞歸程序設計

例1

試編一個遞歸函數，求正整數n的階乘值n！。

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

1n=0

fact(n)=

n*fact(n-1)n>0

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

{intm;

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

else

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

return(m);}

}

例2

試編一個遞歸函數，求第n項Fibonacci級數的值。

假設使用Fibona(n)表示第n項Fibonacci級數的值，

根據Fibonacci級數的計算公式：

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);

}

}

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

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

在遞歸程序的執(zhí)行過程中，每當執(zhí)行函數調用時，必須完成以下任務：

（1）計算當前被調用函數每個實在參數的值；

（2）為當前被調用的函數分配一片存儲空間，用于存放其所需的各種數據，并將這片存儲空間的首地址壓入棧中；

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

（4）控制轉到被調用函數的函數體，從其第一個可執(zhí)行的語句開始執(zhí)行。

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

當從被調用的函數返回時，必須完成以下任務：

（1）如果被調用的函數有返回值，則記下該返回值，同時通過棧頂元素到該被調用函數對應的存儲空間中取出其返回地址；

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

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

例3

試編寫一個遞歸函數，在第一行打印輸出1個1，在第二行打印輸出2個2，……在第n行打印輸出n個n。例如，當n=5時，調用該函數的輸出結果為：

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結束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、遞歸找數組中的最大數2、遞歸倒置數組3、遞歸二分查找4、遞歸倒序遍歷帶頭結點的單鏈表5、全排列問題例5：下面程序的輸出結果：voidprintd(intn){if(n<0){putchar('-');n=-n;}if(n/10)printd(n/10);putchar(n%10+'0');}voidmain(){printd(-1234);}排列問題設計一個遞歸算法生成n個元素{r1,r2,…,rn}的全排列。設R={r1,r2,…,rn}是要進行排列的n個元素，Ri=R-{ri}。集合X中元素的全排列記為perm(X)。(ri)perm(X)表示在全排列perm(X)的每一個排列前加上前綴得到的排列。R的全排列可歸納定義如下：當n=1時，perm(R)=(r)，其中r是集合R中唯一的元素；當n>1時，perm(R)由(r1)perm(R1),(r2)perm(R2)，…，(rn)perm(Rn)構成。按照上面給出的遞歸定義，可設計產生Perm（R）的遞歸算法：

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

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

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

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

5.3遞歸程序到非遞歸程序的轉換

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

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

歸問題為簡單遞歸問題；

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

必須進行試探和回溯，稱這類遞歸問題為復雜

遞歸問題。

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

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

采用非遞歸方式實現求正整數n的階乘值。

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

根據階乘的遞歸定義，不失一般性，顯然有以下遞推關系成立：

1i=0

Fact(i)=

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

階乘問題的非遞歸算法的實現如下：

intFact(intn)

{

inti,fac;

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

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

/*根據遞推關系進行遞推*/

return(fac);

}

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

#defineMAXSIZE100

typedefintdatatype;

typedefstruct{

datatypea[MAXSIZE];

intsize;

}sequence_list;

請分別使用遞歸與非遞歸方式，實現順序表中所有元素的逆轉。例如，假設順序表L含有10個元素，且L.a中所有元素的值為：

562134912332981683

逆轉后L.a中所有元素的排列順序為：

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

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

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

5.3.2復雜遞歸程序到非遞歸程序的轉換5.3.2復雜遞歸程序到非遞歸程序的轉換例7

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

18

3249266103012845

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

641832926121030845

試采用遞歸和非遞歸算法實現該遍歷問題。

Leftmid-1midmid+1right遞歸實現算法如下：

#defineMAXSIZE20

typedefintlistarr[MAXSIZE];

voidlistorder(listarrlist,intleft,intright)

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

intmid;

if(left<=right)

{mid=(left+right)/2;

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

listorder(list,left,mid-1);

listorder(list,mid+1,right);

}

}

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

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

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

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

123456轉入左序列前應保存右序列的位置254925*1608rightleft210123top=-1mid例：

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

123456left與right指向前半部分進行遍歷。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;/*存放待處理數組段的起點下標*/

intr;/*存放待處理數組段的終點下標*/

}stacknode;/*棧中每個元素的類型*/

stacknodestack[MAXSIZE];

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

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

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

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

{/*當前正在處理的數組段非空或棧非空*/

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

{/*當前正在處理的數組段為空時進行回溯*/

i=stack[top].l;

j=stack[top].r;

--top;

}

}

}

}例5.8

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

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

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

設計一個遞歸函數，將一個正整數n轉換成字符串。例如，若n=456，則函數輸出的結果為“456”。n的位數不確定，可以為任意位數的整數。

voidconvert(intn)

{inti;

charch;

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

convert(i);

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

putchar(ch);

}

5．4遞歸程序設計的應用實例例10

試編寫一個遞歸函數，求兩個正整數m和n的最大公約數，其中最大公約數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

已知帶頭結點的單鏈表存儲結構定義如下：

typedefintdatatype;/*預定義的數據類型*/

typedefstructnode

{

datatypedata;/*結點數據域*/

structnode*next;

}linknode;

typedeflinknode*linklist;

請編寫遞歸函數分別順序（從前向后）、倒序（從后向前）輸出單鏈表內容。

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

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

=

a0

+

a1x

+

a2x2

+

…

+

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

≥

0和n

≥

0時的定義為：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已知多項式Fn(x)的定義如下：試寫出計算Fn(x)值的遞歸函數。5.9n階Hanoi塔問題：設有3個分別命名為X，Y和Z的塔座，在塔座X上從上到下放有n個直徑各不相同、編號依次為1，2，3，…，n的圓盤（直徑大的圓盤在下，直徑小的圓盤在上），現要求將X塔座上的n個