【精品課件】遞歸

1、第5章遞 歸,遞歸與遞歸程序設(shè)計(jì),遞歸程序到非遞歸程序的轉(zhuǎn)換,遞歸程序設(shè)計(jì)的應(yīng)用實(shí)例,遞歸程序執(zhí)行過程的分析,5.1 遞歸與遞歸程序設(shè)計(jì) 在一個(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ù)，許多高級(jí)程序設(shè)計(jì)語言均提供了支持遞歸定義的機(jī)制和手段。例1 試編一個(gè)遞歸函數(shù)，求正整數(shù)n的階乘值n！。用fact(n)表示n的階乘值，據(jù)階乘的數(shù)學(xué)定義可知： 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 試編一個(gè)遞歸函數(shù)，求第n項(xiàng)Fibonacci級(jí)數(shù)的值。 假設(shè)使用Fibona(n)表示第n項(xiàng)Fibonacci級(jí)數(shù)的值， 根據(jù)Fibonacci級(jí)數(shù)的計(jì)算公式： 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); ,遞歸程序設(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ù)的修改最終必須保證遞歸出口得以滿足。,52 遞歸程序執(zhí)行過程的分析 在遞歸程序的運(yùn)

4、行過程中，系統(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ù)分配一片存儲(chǔ)空間，用于存放其所需的各種數(shù)據(jù)，并將這片存儲(chǔ)空間的首地址壓入棧中；（3）將當(dāng)前被調(diào)用函數(shù)的實(shí)在參數(shù)、將來當(dāng)前函數(shù)執(zhí)行完畢后的返回地址等數(shù)據(jù)存入上述所分配的存儲(chǔ)空間中；（4）控制轉(zhuǎn)到被調(diào)用函數(shù)的函數(shù)體，從其第一個(gè)可執(zhí)行的語句開始執(zhí)行。,當(dāng)從被調(diào)用的函數(shù)返回時(shí)，必須完成以下任務(wù)： （1）如果被調(diào)用的

5、函數(shù)有返回值，則記下該返回值，同時(shí)通過棧頂元素到該被調(diào)用函數(shù)對應(yīng)的存儲(chǔ)空間中取出其返回地址；（2）把分配給被調(diào)用函數(shù)的那片存儲(chǔ)空間回收，棧頂元素出棧；（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 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)換 采用遞歸方式實(shí)現(xiàn)問題的算法程序具有結(jié)構(gòu)清晰、可讀性好、易于理解等優(yōu)點(diǎn)，但遞歸程序較之非遞歸程序無論是空間需求還是時(shí)間需求都更高，因此在希望節(jié)省存儲(chǔ)空間和追求執(zhí)行效率的情況下，人們更希望使用非遞歸方式實(shí)現(xiàn)問題的算法程序； 另外，有些高級(jí)程序設(shè)計(jì)語言沒有提供遞歸的機(jī)制和手段，對于某些具有

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

9、生計(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)生的算法程序比遞歸算法具有更高的效率。,簡單遞歸問題非遞歸實(shí)現(xiàn)的基本思想：將原問題分解成若干結(jié)構(gòu)與原問題相同，但規(guī)模較小的子問題，并建立原問題與子問題解之間的遞推關(guān)系，然后

10、定義若干變量用于記錄遞推關(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)系成立： 1 i=0 Fact(i)= i* Fact(i-1) i0上述遞推關(guān)系表明

11、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)如下： int Fact ( int n ) int i,fac; fac=1;/*將變量fac初始化為Fact(0)的值*/ for (i=1;i=n; +i)

12、 fac =i*fac; /*根據(jù)遞推關(guān)系進(jìn)行遞推*/ return(fac); 例6 試編寫兩個(gè)函數(shù)，分別使用遞歸方式和非遞歸方式求第n階勒讓德多項(xiàng)式的值。,已知勒讓德多項(xiàng)式的遞歸定義如下： 1 n=0pn(x)= x n=1 (2n-1)xpn-1(x)(n-1)pn-2(x)/n n1遞歸實(shí)現(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、); ,下面考慮該問題的非遞歸實(shí)現(xiàn)：根據(jù)勒讓德多項(xiàng)式的定義，當(dāng)n1時(shí)，第n階多項(xiàng)式的值是建立在第n-1階多項(xiàng)式的值和第n-2階多項(xiàng)式的值的基礎(chǔ)上?？紤]一般情況，當(dāng)i1時(shí)，第i階多項(xiàng)式的值應(yīng)該建立在第i-1階多項(xiàng)式的值和第i-2階多項(xiàng)式的值的基礎(chǔ)上。如果仍然采用p(n,x)表示第n階勒讓德多項(xiàng)式的值，則在i1的情況下有如下遞推關(guān)系成立： p(i,x)=(2i-1)xp(i-1,x)(i-1)p(i-2,x)/i 顯然，可以利用以上遞推關(guān)系，從i=2開始，逐步增大i的值，依次求解第i階勒讓德多項(xiàng)式的值；當(dāng)i=n時(shí)，便求到了p(n,x)的值。在整個(gè)求解過程中不需要進(jìn)行試探和回溯，因而該問題屬于簡單遞

14、歸問題，完全可以使用遞推技術(shù)加以實(shí)現(xiàn)。,在具體實(shí)現(xiàn)時(shí)可以定義兩個(gè)變量pre1和pre2，分別記錄上述遞推關(guān)系中兩個(gè)子問題的解，即pre1=p(i-2,x)，pre2=p(i-1,x)，且pre1和pre2的值始終隨著i的值的改變而發(fā)生變化：每當(dāng)新求出第i階多項(xiàng)式的值后，i的值要增加1，而在此之前應(yīng)該修改pre1和pre2的值，用pre1記錄pre2當(dāng)前的值，而用pre2記錄新求出的多項(xiàng)式的值，直至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 復(fù)雜遞歸程序到非遞歸程序的轉(zhuǎn)換 復(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)。例7 按中點(diǎn)優(yōu)先的順序遍

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

17、arrMAXSIZE;void listorder(listarr list, int left, int right) /*將數(shù)組段listleft.right的元素按中點(diǎn)優(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,下面考慮該問題的非遞歸實(shí)現(xiàn)：在線性表的遍歷過程中，輸出中點(diǎn)的值后，中點(diǎn)將線性表分成前半部分和后半部分。接下

18、來應(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é)束。,#define

19、MAXSIZE 20typedef int listarrMAXSIZE;void listorder(listarr list,int left, int right) typedef struct int l; /*存放待處理數(shù)組段的起點(diǎn)下標(biāo)*/ int r; /*存放待處理數(shù)組段的終點(diǎn)下標(biāo)*/ stacknode; /*棧中每個(gè)元素的類型*/ stacknode stackMAXSIZE; int top,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”,listmid); +top; stacktop.l=mid+1; stacktop.r=j; j=mid-1; else /*當(dāng)前正在處理的數(shù)組段為空時(shí)進(jìn)