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

遞歸

3遞歸算法到非遞歸算法的轉(zhuǎn)換1什么是遞歸2遞歸算法的設(shè)計(jì)1.1什么是遞歸1.1遞歸的定義

在定義一個(gè)過程或函數(shù)時(shí)出現(xiàn)調(diào)用本過程或本函數(shù)的成分,稱之為遞歸。若調(diào)用自身,稱之為直接遞歸。若過程或函數(shù)p調(diào)用過程或函數(shù)q,而q又調(diào)用p,稱之為間接遞歸。如果一個(gè)遞歸過程或遞歸函數(shù)中遞歸調(diào)用語句是最后一條執(zhí)行語句,則稱這種遞歸調(diào)用為尾遞歸。2.例1以下是求n!(n為正整數(shù))的遞歸函數(shù)。intfun(intn){intx;if(n==1) /*語句1*/x=1; /*語句2*/else /*語句3*/x=fun(n-1)*n; /*語句4*/return(x); /*語句5*/}在該函數(shù)fun(n)求解過程中,直接調(diào)用fun(n-1)(語句4)自身,所以它是一個(gè)直接遞歸函數(shù)。又由于遞歸調(diào)用是最后一條語句,所以它又屬于尾遞歸。3.1.2何時(shí)使用遞歸在以下三種情況下,常常要用到遞歸的方法。

1.定義是遞歸的有許多數(shù)學(xué)公式、數(shù)列等的定義是遞歸的。例如,求n!和Fibonacci數(shù)列等。這些問題的求解過程可以將其遞歸定義直接轉(zhuǎn)化為對應(yīng)的遞歸算法。4.2.

數(shù)據(jù)結(jié)構(gòu)是遞歸的

有些數(shù)據(jù)結(jié)構(gòu)是遞歸的。例如,第2章中介紹過的單鏈表就是一種遞歸數(shù)據(jù)結(jié)構(gòu),其結(jié)點(diǎn)類型定義如下：typedefstructLNode{ElemTypedata;structLNode*next; }LinkList;該定義中,結(jié)構(gòu)體LNode的定義中用到了它自身,即指針域next是一種指向自身類型的指針,所以它是一種遞歸數(shù)據(jù)結(jié)構(gòu)。5.對于遞歸數(shù)據(jù)結(jié)構(gòu),采用遞歸的方法編寫算法既方便又有效。例如,求一個(gè)不帶頭結(jié)點(diǎn)的單鏈表head的所有data域(假設(shè)為int型)之和的遞歸算法如下：intSum(LinkList*head){if(head==NULL)return0;elsereturn(head->data+Sum(head->next));}6.3.

問題的求解方法是遞歸的

有些問題的解法是遞歸的,典型的有Hanoi問題求解,該問題描述是：設(shè)有3個(gè)分別命名為X,Y和Z的塔座,在塔座X上有n個(gè)直徑各不相同,從小到大依次編號(hào)為1,2,…,n的盤片,現(xiàn)要求將X塔座上的n個(gè)盤片移到塔座Z上并仍按同樣順序疊放,盤片移動(dòng)時(shí)必須遵守以下規(guī)則：每次只能移動(dòng)一個(gè)盤片；盤片可以插在X,Y和Z中任一塔座；任何時(shí)候都不能將一個(gè)較大的盤片放在較小的盤片上。設(shè)計(jì)遞歸求解算法,并將其轉(zhuǎn)換為非遞歸算法。設(shè)Hanoi(n,x,y,z)表示將n個(gè)盤片從x通過y移動(dòng)到z上,遞歸分解的過程是：7.Hanoi(n,x,y,z)Hanoi(n-1,x,z,y)；move(n,x,z):將第n個(gè)圓盤從x移到z；Hanoi(n-1,y,x,z)8.1.3遞歸模型

遞歸模型是遞歸算法的抽象,它反映一個(gè)遞歸問題的遞歸結(jié)構(gòu),例如,前面的遞歸算法對應(yīng)的遞歸模型如下：fun(1)=1(1)fun(n)=n*fun(n-1)n>1(2)其中,第一個(gè)式子給出了遞歸的終止條件,第二個(gè)式子給出了fun(n)的值與fun(n-1)的值之間的關(guān)系,我們把第一個(gè)式子稱為遞歸出口,把第二個(gè)式子稱為遞歸體。9.一般地,一個(gè)遞歸模型是由遞歸出口和遞歸體兩部分組成,前者確定遞歸到何時(shí)結(jié)束,后者確定遞歸求解時(shí)的遞推關(guān)系。遞歸出口的一般格式如下：f(s1)=m1 (3.1)這里的s1與m1均為常量,有些遞歸問題可能有幾個(gè)遞歸出口。遞歸體的一般格式如下：f(sn+1)=g(f(si),f(si+1),…,f(sn),cj,cj+1,…,cm) (3.2)其中,n,i,j,m均為正整數(shù)。這里的sn+1是一個(gè)遞歸“大問題”,si,si+1,…,sn為遞歸“小問題”,cj,cj+1,…,cm是若干個(gè)可以直接(用非遞歸方法)解決的問題,g是一個(gè)非遞歸函數(shù),可以直接求值。10.實(shí)際上,遞歸思路是把一個(gè)不能或不好直接求解的“大問題”轉(zhuǎn)化成一個(gè)或幾個(gè)“小問題”來解決,再把這些“小問題”進(jìn)一步分解成更小的“小問題”來解決,如此分解,直至每個(gè)“小問題”都可以直接解決(此時(shí)分解到遞歸出口)。但遞歸分解不是隨意的分解,遞歸分解要保證“大問題”與“小問題”相似,即求解過程與環(huán)境都相似。11.為了討論方便,簡化上述遞歸模型為：f(s1)=m1 (3)f(sn)=g(f(sn-1),c) (4)求f(sn)的分解過程如下：f(sn)↓f(sn-1)↓…↓f(s2)↓f(s1)12.

一旦遇到遞歸出口,分解過程結(jié)束,開始求值過程,所以分解過程是“量變”過程,即原來的“大問題”在慢慢變小,但尚未解決,遇到遞歸出口后,便發(fā)生了“質(zhì)變”,即原遞歸問題便轉(zhuǎn)化成直接問題。上面的求值過程如下：

f(s1)=m1↓f(s2)=g(f(s1),c1)↓f(s3)=g(f(s2),c2)↓…↓f(sn)=g(f(sn-1),cn-1)13.這樣f(sn)便計(jì)算出來了,因此,遞歸的執(zhí)行過程由分解和求值兩部分構(gòu)成。14.求解fun(5)的過程如下：15.2遞歸算法的設(shè)計(jì)遞歸的求解的過程均有這樣的特征：先將整個(gè)問題劃分為若干個(gè)子問題,通過分別求解子問題,最后獲得整個(gè)問題的解。而這些子問題具有與原問題相同的求解方法,于是可以再將它們劃分成若干個(gè)子問題,分別求解,如此反復(fù)進(jìn)行,直到不能再劃分成子問題,或已經(jīng)可以求解為止。這種自上而下將問題分解、求解,再自上而下引用、合并,求出最后解答的過程稱為遞歸求解過程。這是一種分而治之的算法設(shè)計(jì)方法。遞歸算法設(shè)計(jì)先要給出遞歸模型,再轉(zhuǎn)換成對應(yīng)的C/C++語言函數(shù)。16.遞歸設(shè)計(jì)的步驟如下：

(1)對原問題f(s)進(jìn)行分析,假設(shè)出合理的“較小問題”f(s')(與數(shù)學(xué)歸納法中假設(shè)n=k-1時(shí)等式成立相似)；(2)假設(shè)f(s')是可解的,在此基礎(chǔ)上確定f(s)的解,即給出f(s)與f(s')之間的關(guān)系(與數(shù)學(xué)歸納法中求證n=k時(shí)等式成立的過程相似)；(3)確定一個(gè)特定情況(如f(1)或f(0))的解,由此作為遞歸出口(與數(shù)學(xué)歸納法中求證n=1時(shí)等式成立相似)。17.

例如,采用遞歸算法求實(shí)數(shù)數(shù)組A[0..n-1]中的最小值。假設(shè)f(A,i)函數(shù)求數(shù)組元素A[0]～A[i]中的最小值。當(dāng)i=0時(shí),有f(A,i)=A[0]；假設(shè)f(A,i-1)已求出,則f(A,i)=MIN(f(A,i-1),A[i]),其中MIN()為求兩個(gè)值較小值函數(shù)。因此得到如下遞歸模型：A[0] 當(dāng)i=0時(shí)f(A,i)=MIN(f(A,i-1),A[i]) 其他情況18.由此得到如下遞歸求解算法：floatf(floatA[],inti){floatm;if(i==0)returnA[0];else{m=f(A,i-1); if(m>A[i])returnA[i]; elsereturnm; }}

19.3遞歸算法到非遞歸算法的轉(zhuǎn)換

遞歸算法有兩個(gè)基本特性：一是遞歸算法是一種分而治之的、把復(fù)雜問題分解為簡單問題的求解問題方法,對求解某些復(fù)雜問題,遞歸算法分析問題的方法是十分有效的；二是遞歸算法的時(shí)間效率通常比較差。因此,對求解某些問題時(shí),我們希望用遞歸算法分析問題,用非遞歸算法具體求解問題。這就需要把遞歸算法轉(zhuǎn)換為非遞歸算法。20.把遞歸算法轉(zhuǎn)化為非遞歸算法有如下三種基本方法：

(1)對于尾遞歸和單向遞歸的算法,可用循環(huán)結(jié)構(gòu)的算法替代。(2)自己用棧模擬系統(tǒng)的運(yùn)行時(shí)棧,通過分析只保存必須保存的信息,從而用非遞歸算法替代遞歸算法。(3)利用棧保存參數(shù),由于棧的后進(jìn)先出特性吻合遞歸算法的執(zhí)行過程,因而可以用非遞歸算法替代遞歸算法。本節(jié)討論第(1)種和第(2)種情況的遞歸算法轉(zhuǎn)化為非遞歸算法的問題,前者是一種是直接轉(zhuǎn)化法,不需要使用棧,后者是間接轉(zhuǎn)化法,需要使用棧。第(3)種情況也需要使用棧,但因具體情況而異,例如樹的遍歷算法。21.3.1尾遞歸和單向遞歸的消除

采用循環(huán)結(jié)構(gòu)消除尾遞歸和單向遞歸。求解Fibonacci數(shù)列的算法如下：

intFib(intn){inti,f1,f2,f3;if(n==1||n==2)return(n);f1=1;f2=2;for(i=3;i<=n;i++){f3=f1+f2;f1=f2;f2=f3;}return(f3);}22.

采用循環(huán)結(jié)構(gòu)消除遞歸沒有通用的轉(zhuǎn)換算法,對于具體問題要深入分析對應(yīng)的遞歸結(jié)構(gòu),設(shè)計(jì)有效的循環(huán)語句進(jìn)行遞歸到非遞歸的轉(zhuǎn)換。23.3.2模擬系統(tǒng)的運(yùn)行時(shí)棧消除遞歸

對于不屬于尾遞歸和單向遞歸的遞歸算法,很難轉(zhuǎn)化為與之等價(jià)的循環(huán)算法。但所有的遞歸程序都可以轉(zhuǎn)化為與之等價(jià)的非遞歸程序，有一個(gè)通用的算法可以將遞歸程序轉(zhuǎn)化為非遞歸程序由于這個(gè)算法過于通用,比較復(fù)雜,不易理解,而且通常需要使用goto轉(zhuǎn)移語句,違反結(jié)構(gòu)化程序設(shè)計(jì)規(guī)定,因此,在這里不作介紹。下面討論直接使用棧保存中間結(jié)果,從而將遞歸算法轉(zhuǎn)化為非遞歸算法的過程。24.

仍以例1的遞歸算法進(jìn)行討論,其遞歸模型有一個(gè)遞歸出口和一個(gè)遞歸體兩個(gè)式子,分別稱為(1)式和(2)式。設(shè)計(jì)一個(gè)棧,其結(jié)構(gòu)如下：

struct{ intvn; /*保存n值*/ intvf; /*保存fun1(n)值*/ inttag;/*標(biāo)識(shí)是否求出fun1(n)值,1:未求出,0:已求出*/}St[MaxSize]; /*定義棧*/25.計(jì)算fun1(5)的過程如下：將(5,*,1)進(jìn)棧;while(棧不空){if(未計(jì)算出棧頂元素的vf值即St[top].tag==1){if(棧頂元素滿足(1)式) 求出對應(yīng)的St[top].vf值,并置St[top].tag=0;else/*棧頂元素滿足(2)式*/ 將(St[top].vn-1,*,1)進(jìn)棧;}elseif(棧頂元素已計(jì)算出棧頂元素的vf值即St[top].tag==0) 顯然棧頂元素由次棧頂元素通過(2)式分解得到的,回過來由棧頂元素的vf值計(jì)算出次棧頂元素的vf值并退棧;if(棧中只有一個(gè)已求出vf值的元素)退出循環(huán);}26.對應(yīng)的非遞歸fun1算法如下：

intfun1(intn){top++; /*初值進(jìn)棧*/St[top].vn=n;St[top].tag=1;while(top>-1) /*棧不空時(shí)循環(huán)*/ {if(St[top].tag==1)/*未計(jì)算出棧頂元素的vf