1、第5章遞 歸,遞歸與遞歸程序設計,遞歸程序到非遞歸程序的轉(zhuǎn)換,遞歸程序設計的應用實例,遞歸程序執(zhí)行過程的分析,5.1 遞歸與遞歸程序設計 在一個函數(shù)的定義中出現(xiàn)了對自己本身的調(diào)用，稱之為直接遞歸；或者一個函數(shù)p的定義中包含了對函數(shù)q的調(diào)用，而q的實現(xiàn)過程又調(diào)用了p，即函數(shù)調(diào)用形成了一個環(huán)狀調(diào)用鏈, 這種方式稱之為間接遞歸。遞歸技術在算法和程序設計中是一種十分有用的技術，許多高級程序設計語言均提供了支持遞歸定義的機制和手段。例1 試編一個遞歸函數(shù)，求正整數(shù)n的階乘值n！。用fact(n)表示n的階乘值，據(jù)階乘的數(shù)學定義可知： 1 n=0 fact(n) = n*fact(n-1) n0,該問題的

2、算法為： int Fact ( int n ) int m; if (n= =0) return(1); else m=n*Fact(n-1); return(m); 例2 試編一個遞歸函數(shù)，求第n項Fibonacci級數(shù)的值。 假設使用Fibona(n)表示第n項Fibonacci級數(shù)的值， 根據(jù)Fibonacci級數(shù)的計算公式： 1 n=1 Fibona(n)= 1 n=2 Fibona(n-1)+ Fibona(n-2) n2,該問題的算法為： int Fibona ( int n ) int m; if (n= =1) return (1); else if (n= =2) retur

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

4、行過程中，系統(tǒng)內(nèi)部設立了一個棧，用于存放每次函數(shù)調(diào)用與返回所需的各種數(shù)據(jù)，主要包括：函數(shù)調(diào)用執(zhí)行完成時的返回地址、函數(shù)的返回值、每次函數(shù)調(diào)用的實在參數(shù)和局部變量。 在遞歸程序的執(zhí)行過程中，每當執(zhí)行函數(shù)調(diào)用時，必須完成以下任務：（1）計算當前被調(diào)用函數(shù)每個實在參數(shù)的值；（2）為當前被調(diào)用的函數(shù)分配一片存儲空間，用于存放其所需的各種數(shù)據(jù)，并將這片存儲空間的首地址壓入棧中；（3）將當前被調(diào)用函數(shù)的實在參數(shù)、將來當前函數(shù)執(zhí)行完畢后的返回地址等數(shù)據(jù)存入上述所分配的存儲空間中；（4）控制轉(zhuǎn)到被調(diào)用函數(shù)的函數(shù)體，從其第一個可執(zhí)行的語句開始執(zhí)行。,當從被調(diào)用的函數(shù)返回時，必須完成以下任務： （1）如果被調(diào)用的

5、函數(shù)有返回值，則記下該返回值，同時通過棧頂元素到該被調(diào)用函數(shù)對應的存儲空間中取出其返回地址；（2）把分配給被調(diào)用函數(shù)的那片存儲空間回收，棧頂元素出棧；（3）按照被調(diào)用函數(shù)的返回地址返回到調(diào)用點，若有返回值，還必須將返回值傳遞給調(diào)用者，并繼續(xù)程序的執(zhí)行。,例3 試編寫一個遞歸函數(shù)，在第一行打印輸出1個1，在第二行打印輸出2個2， 在第n行打印輸出n個n。例如，當n=5時，調(diào)用該函數(shù)的輸出結(jié)果為： 1 2 2 3 3 3 4 4 4 4 5 5 5 5 5該問題的算法為:print ( int n ) int i; if (n!=0) print(n-1); for(i=1;i=n;i+) pri

6、ntf(%d,n); printf(n); ,Print(5),print(4),print(3),print(2),print(1),print(0),(1),(2),(3),(4),(5),(6),(7),(8),(9),(10),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); 1,return(1),(4),retu

7、rn(1),(5),return(1),(6),(7),(8),(9),return(1),return(1),(10),Fibona(5)的執(zhí)行過程,S1,S2,S3,1,1,1,2,3,(11),(12),(13),(14),1,(15),(17),(18),5,2,例4:,5.3 遞歸程序到非遞歸程序的轉(zhuǎn)換 采用遞歸方式實現(xiàn)問題的算法程序具有結(jié)構(gòu)清晰、可讀性好、易于理解等優(yōu)點，但遞歸程序較之非遞歸程序無論是空間需求還是時間需求都更高，因此在希望節(jié)省存儲空間和追求執(zhí)行效率的情況下，人們更希望使用非遞歸方式實現(xiàn)問題的算法程序； 另外，有些高級程序設計語言沒有提供遞歸的機制和手段，對于某些具有

8、遞歸性質(zhì)的問題（簡稱遞歸問題）無法使用遞歸方式加以解決，必須使用非遞歸方式實現(xiàn)。因此，本小節(jié)主要研究遞歸程序到非遞歸程序的轉(zhuǎn)換方法。,一般而言，求解遞歸問題有兩種方式：（1）在求解過程中直接求值，無需回溯。稱這類遞 歸問題為簡單遞歸問題；（2）另一類遞歸問題在求解過程中不能直接求值， 必須進行試探和回溯，稱這類遞歸問題為復雜 遞歸問題。 兩類遞歸問題在轉(zhuǎn)換成非遞歸方式實現(xiàn)時所采用的方法是不同的。通常簡單遞歸問題可以采用遞推方法直接求解；而復雜遞歸問題由于要進行回溯，在實現(xiàn)過程中必須借助棧來管理和記憶回溯點。,5.3.1 簡單遞歸程序到非遞歸程序的轉(zhuǎn)換 采用遞歸技術求解問題的算法程序是自頂向下產(chǎn)

9、生計算序列，其缺點之一是導致程序執(zhí)行過程中許多重復的函數(shù)調(diào)用。遞推技術同樣以分劃技術為基礎，它也要求將需求解的問題分劃成若干與原問題結(jié)構(gòu)相同、但規(guī)模較小的子問題；與遞歸技術不同的是，遞推方法是采用自底向上的方式產(chǎn)生計算序列，其首先計算規(guī)模最小的子問題的解，然后在此基礎上依次計算規(guī)模較大的子問題的解，直到最后產(chǎn)生原問題的解。由于求解過程中每一步新產(chǎn)生的結(jié)果總是直接以前面已有的計算結(jié)果為基礎，避免了許多重復的計算，因而遞推方法產(chǎn)生的算法程序比遞歸算法具有更高的效率。,簡單遞歸問題非遞歸實現(xiàn)的基本思想：將原問題分解成若干結(jié)構(gòu)與原問題相同，但規(guī)模較小的子問題，并建立原問題與子問題解之間的遞推關系，然后

10、定義若干變量用于記錄遞推關系的每個子問題的解；程序的執(zhí)行便是根據(jù)遞推關系，不斷修改這些變量的值，使之成為更大子問題的解的過程；當?shù)玫皆瓎栴}解時，遞推過程便可結(jié)束了。例5 采用非遞歸方式實現(xiàn)求正整數(shù)n的階乘值。 仍使用Fact(n)表示n的階乘值。要求解Fact(n)的值，可以考慮i從0開始，依次取1,2,，一直到n，分別求Fact(i)的值，且保證求解Fact(i)時總是以前面已有的求解結(jié)果為基礎；當i=n 時，F(xiàn)act(i)的值即為所求的Fact(n)的值。,根據(jù)階乘的遞歸定義，不失一般性，顯然有以下遞推關系成立： 1 i=0 Fact(i)= i* Fact(i-1) i0上述遞推關系表明

11、Fact(i)是建立于Fact(i-1)的基礎上的，在求解Fact(i)時子問題只有一個Fact(i-1)，且整個Fact(n)的求解過程無需回溯，因此該問題屬于簡單遞歸問題，可以使用遞推技術加以實現(xiàn)，實現(xiàn)過程中只需定義一個變量fac始終記錄子問題Fact(i-1)的值。初始時，i=1,fac= Fact(i-1)= Fact(0)=1；在此基礎上根據(jù)以上遞推關系不斷向前遞推，使i的值加大，直至i=n為止。,階乘問題的非遞歸算法的實現(xiàn)如下： int Fact ( int n ) int i,fac; fac=1;/*將變量fac初始化為Fact(0)的值*/ for (i=1;i=n; +i)

12、 fac =i*fac; /*根據(jù)遞推關系進行遞推*/ return(fac); 例6 試編寫兩個函數(shù)，分別使用遞歸方式和非遞歸方式求第n階勒讓德多項式的值。,已知勒讓德多項式的遞歸定義如下： 1 n=0pn(x)= x n=1 (2n-1)xpn-1(x)(n-1)pn-2(x)/n n1遞歸實現(xiàn)算法： float p(int n, float x) float p1,p2; if (n=0) return(1.0); else if (n=1) return(x); else p1=(2*n-1)*x*p(n-1,x); p2=(n-1)*p(n-2,x); return(p1-p2)/n

13、); ,下面考慮該問題的非遞歸實現(xiàn)：根據(jù)勒讓德多項式的定義，當n1時，第n階多項式的值是建立在第n-1階多項式的值和第n-2階多項式的值的基礎上?？紤]一般情況，當i1時，第i階多項式的值應該建立在第i-1階多項式的值和第i-2階多項式的值的基礎上。如果仍然采用p(n,x)表示第n階勒讓德多項式的值，則在i1的情況下有如下遞推關系成立： p(i,x)=(2i-1)xp(i-1,x)(i-1)p(i-2,x)/i 顯然，可以利用以上遞推關系，從i=2開始，逐步增大i的值，依次求解第i階勒讓德多項式的值；當i=n時，便求到了p(n,x)的值。在整個求解過程中不需要進行試探和回溯，因而該問題屬于簡單遞

14、歸問題，完全可以使用遞推技術加以實現(xiàn)。,在具體實現(xiàn)時可以定義兩個變量pre1和pre2，分別記錄上述遞推關系中兩個子問題的解，即pre1=p(i-2,x)，pre2=p(i-1,x)，且pre1和pre2的值始終隨著i的值的改變而發(fā)生變化：每當新求出第i階多項式的值后，i的值要增加1，而在此之前應該修改pre1和pre2的值，用pre1記錄pre2當前的值，而用pre2記錄新求出的多項式的值，直至i=n。 float p ( int n, float x ) float pre1,pre2,a,b,valuep; int i; if (n=0) return(1.0); else if (n=

15、1) return(x);,else pre1=1.0; pre2=x; for (i=2;i=n;+i) a=2*i-1; b=i-1; valuep=(a*pre2*x-b*pre1)/i; pre1=pre2; pre2=valuep; return(valuep); ,5.3.2 復雜遞歸程序到非遞歸程序的轉(zhuǎn)換 復雜遞歸問題在求解的過程中無法保證求解動作一直向前，往往需要設置一些回溯點，當求解無法進行下去或當前處理的工作已經(jīng)完成時，必須退回到所設置的回溯點，繼續(xù)問題的求解。因此，在使用非遞歸方式實現(xiàn)一個復雜遞歸問題的算法時，經(jīng)常使用棧來記錄和管理所設置的回溯點。例7 按中點優(yōu)先的順序遍

16、歷線性表問題：已知線性表list以順序存儲方式存儲，要求按以下順序輸出list中所有結(jié)點的值：首先輸出線性表list中點位置上的元素值，然后輸出中點左部所有元素的值，再輸出中點右部所有元素的值；而無論輸出中點左部所有元素的值還是輸出中點右部所有元素的值，也均應遵循以上規(guī)律。,例如，已知數(shù)組list中元素的值為： 18 32 4 9 26 6 10 30 12 8 45則list中元素按中點優(yōu)先順序遍歷的輸出結(jié)果為： 6 4 18 32 9 26 12 10 30 8 45試采用遞歸和非遞歸算法實現(xiàn)該遍歷問題。遞歸實現(xiàn)算法如下：#define MAXSIZE 20typedef int list

17、arrMAXSIZE;void listorder(listarr list, int left, int right) /*將數(shù)組段listleft.right的元素按中點優(yōu)先順序輸出*/ int mid; if (left=right) mid=(left+right)/2; printf(%4d,listmid); listorder(list,left,mid-1); listorder(list,mid+1,right); ,Left mid-1 mid mid+1 right,下面考慮該問題的非遞歸實現(xiàn)：在線性表的遍歷過程中，輸出中點的值后，中點將線性表分成前半部分和后半部分。接下

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

19、MAXSIZE 20typedef int listarrMAXSIZE;void listorder(listarr list,int left, int right) typedef struct int l; /*存放待處理數(shù)組段的起點下標*/ int r; /*存放待處理數(shù)組段的終點下標*/ stacknode; /*棧中每個元素的類型*/ stacknode stackMAXSIZE; int top,i,j,mid; /*top為棧頂指針*/ if (left=right) /*數(shù)組段不為空*/ top= -1; i=left; j=right; while (i=j | top!=-1) /*當前正在處理的數(shù)組段非空或棧非空*/,if (i=j) mid=(i+j)/2; printf(“%4d”,listmid); +top; stacktop.l=mid+1; stacktop.r=j; j=mid-1; else /*當前正在處理的數(shù)組段為空時進