1、第6章 遞歸,6.3 遞歸算法到非遞歸算法的轉(zhuǎn)換,6.1 什么是遞歸,6.2 遞歸算法的設(shè)計,本章小結(jié),6.1 什么是遞歸 6.1.1 遞歸的定義 在定義一個過程或函數(shù)時出現(xiàn)調(diào)用本過程或本函數(shù)的成分，稱之為遞歸。若調(diào)用自身，稱之為直接遞歸。若過程或函數(shù)p調(diào)用過程或函數(shù)q，而q又調(diào)用p，稱之為間接遞歸。 如果一個遞歸過程或遞歸函數(shù)中遞歸調(diào)用語句是最后一條執(zhí)行語句，則稱這種遞歸調(diào)用為尾遞歸。,例6.1 以下是求n!（n為正整數(shù)）的遞歸函數(shù)。 int fun(int n) int x; if (n=1) /*語句1*/ x=1;/*語句2*/ else /*語句3*/ x=fun(n-1)*n;/*

2、語句4*/ return(x);/*語句5*/ 在該函數(shù)fun(n)求解過程中，直接調(diào)用fun(n-1)（語句4）自身，所以它是一個直接遞歸函數(shù)。又由于遞歸調(diào)用是最后一條語句，所以它又屬于尾遞歸。,6.1.2 何時使用遞歸 在以下三種情況下，常常要用到遞歸的方法。 1. 定義是遞歸的 有許多數(shù)學(xué)公式、數(shù)列等的定義是遞歸的。例如，求n!和Fibonacci數(shù)列等。這些問題的求解過程可以將其遞歸定義直接轉(zhuǎn)化為對應(yīng)的遞歸算法。,2. 數(shù)據(jù)結(jié)構(gòu)是遞歸的 有些數(shù)據(jù)結(jié)構(gòu)是遞歸的。例如，第2章中介紹過的單鏈表就是一種遞歸數(shù)據(jù)結(jié)構(gòu)，其結(jié)點類型定義如下： typedef struct LNode ElemTyp

3、e data; struct LNode *next; LinkList; 該定義中，結(jié)構(gòu)體LNode的定義中用到了它自身，即指針域next是一種指向自身類型的指針，所以它是一種遞歸數(shù)據(jù)結(jié)構(gòu)。,對于遞歸數(shù)據(jù)結(jié)構(gòu)，采用遞歸的方法編寫算法既方便又有效。例如，求一個不帶頭結(jié)點的單鏈表head的所有data域（假設(shè)為int型）之和的遞歸算法如下： int Sum(LinkList *head) if (head=NULL) return 0; else return(head-data+Sum(head-next); ,3. 問題的求解方法是遞歸的 有些問題的解法是遞歸的，典型的有Hanoi問題求解，

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

5、歸模型 遞歸模型是遞歸算法的抽象，它反映一個遞歸問題的遞歸結(jié)構(gòu)，例如，前面的遞歸算法對應(yīng)的遞歸模型如下： fun(1)=1 (1) fun(n)=n*fun(n-1) n1 (2) 其中，第一個式子給出了遞歸的終止條件，第二個式子給出了fun(n)的值與fun(n-1)的值之間的關(guān)系，我們把第一個式子稱為遞歸出口，把第二個式子稱為遞歸體。,一般地，一個遞歸模型是由遞歸出口和遞歸體兩部分組成，前者確定遞歸到何時結(jié)束，后者確定遞歸求解時的遞推關(guān)系。遞歸出口的一般格式如下： f(s1)=m1 (6.1) 這里的s1與m1均為常量，有些遞歸問題可能有幾個遞歸出口。遞歸體的一般格式如下： f(sn+1)

6、=g(f(si),f(si+1),f(sn),cj,cj+1,cm) (6.2) 其中，n，i，j，m均為正整數(shù)。這里的sn+1是一個遞歸“大問題”，si，si+1，sn為遞歸“小問題”，cj，cj+1，cm是若干個可以直接（用非遞歸方法）解決的問題，g是一個非遞歸函數(shù)，可以直接求值。,實際上，遞歸思路是把一個不能或不好直接求解的“大問題”轉(zhuǎn)化成一個或幾個“小問題”來解決，再把這些“小問題”進(jìn)一步分解成更小的“小問題”來解決，如此分解，直至每個“小問題”都可以直接解決（此時分解到遞歸出口）。但遞歸分解不是隨意的分解，遞歸分解要保證“大問題”與“小問題”相似，即求解過程與環(huán)境都相似。,為了討論方

7、便，簡化上述遞歸模型為： f(s1)=m1(6.3) f(sn)=g(f(sn-1),c)(6.4) 求f(sn)的分解過程如下： f(sn) f(sn-1) f(s2) f(s1),一旦遇到遞歸出口，分解過程結(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) 這樣f(sn)便計算出來了，因此，遞歸的執(zhí)行過程由分解和求值兩部分構(gòu)成。,求解f

8、un(5)的過程如下：,6.2 遞歸算法的設(shè)計 遞歸的求解的過程均有這樣的特征：先將整個問題劃分為若干個子問題，通過分別求解子問題，最后獲得整個問題的解。而這些子問題具有與原問題相同的求解方法，于是可以再將它們劃分成若干個子問題，分別求解，如此反復(fù)進(jìn)行，直到不能再劃分成子問題，或已經(jīng)可以求解為止。這種自上而下將問題分解、求解，再自上而下引用、合并，求出最后解答的過程稱為遞歸求解過程。這是一種分而治之的算法設(shè)計方法。 遞歸算法設(shè)計先要給出遞歸模型，再轉(zhuǎn)換成對應(yīng)的C/C+語言函數(shù)。,遞歸設(shè)計的步驟如下： （1）對原問題f(s)進(jìn)行分析，假設(shè)出合理的“較小問題”f(s)（與數(shù)學(xué)歸納法中假設(shè)n=k-1

9、時等式成立相似）； （2）假設(shè)f(s)是可解的，在此基礎(chǔ)上確定f(s)的解，即給出f(s)與f(s)之間的關(guān)系（與數(shù)學(xué)歸納法中求證n=k時等式成立的過程相似）； （3）確定一個特定情況（如f(1)或f(0)）的解，由此作為遞歸出口（與數(shù)學(xué)歸納法中求證n=1時等式成立相似）。,例如，采用遞歸算法求實數(shù)數(shù)組A0.n-1中的最小值。 假設(shè)f(A,i)函數(shù)求數(shù)組元素A0Ai中的最小值。當(dāng)i=0時，有f(A,i)=A0；假設(shè)f(A,i-1)已求出，則f(A,i)=MIN(f(A,i-1),Ai)，其中MIN()為求兩個值較小值函數(shù)。因此得到如下遞歸模型： A0 當(dāng)i=0時 f(A,i)= MIN(f(A

10、,i-1),Ai) 其他情況 由此得到如下遞歸求解算法： float f(float A,int i) float m; if (i=0) return A0; else m=f(A,i-1); if (mAi) return Ai; else return m; ,6.3 遞歸算法到非遞歸算法的轉(zhuǎn)換 遞歸算法有兩個基本特性：一是遞歸算法是一種分而治之的、把復(fù)雜問題分解為簡單問題的求解問題方法，對求解某些復(fù)雜問題，遞歸算法分析問題的方法是十分有效的；二是遞歸算法的時間效率通常比較差。因此，對求解某些問題時，我們希望用遞歸算法分析問題，用非遞歸算法具體求解問題。這就需要把遞歸算法轉(zhuǎn)換為非遞歸算法

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

12、和單向遞歸。求解Fibonacci數(shù)列的算法如下： int Fib(int n) int i,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); ,采用循環(huán)結(jié)構(gòu)消除遞歸沒有通用的轉(zhuǎn)換算法，對于具體問題要深入分析對應(yīng)的遞歸結(jié)構(gòu)，設(shè)計有效的循環(huán)語句進(jìn)行遞歸到非遞歸的轉(zhuǎn)換。,6.3.2 模擬系統(tǒng)的運行時棧消除遞歸 對于不屬于尾遞歸和單向遞歸的遞歸算法，很難轉(zhuǎn)化為與之等價的循環(huán)算法。但所有的遞歸程序都可以轉(zhuǎn)化為與之等價的非遞歸程序（例如，C/C+語言就是先將

13、遞歸程序轉(zhuǎn)化為非遞歸程序，然后求解的），有一個通用的算法可以將遞歸程序轉(zhuǎn)化為非遞歸程序（詳見參考文獻(xiàn)28.4節(jié)），由于這個算法過于通用，比較復(fù)雜，不易理解，而且通常需要使用goto轉(zhuǎn)移語句，違反結(jié)構(gòu)化程序設(shè)計規(guī)定，因此，在這里不作介紹。 下面討論直接使用棧保存中間結(jié)果，從而將遞歸算法轉(zhuǎn)化為非遞歸算法的過程。,仍以例6.1的遞歸算法進(jìn)行討論，其遞歸模型有一個遞歸出口和一個遞歸體兩個式子，分別稱為（1）式和（2）式。設(shè)計一個棧，其結(jié)構(gòu)如下： struct int vn; /*保存n值*/ int vf; /*保存fun1(n)值*/ int tag; /*標(biāo)識是否求出fun1(n)值,1:未求出,

14、0:已求出*/ StMaxSize;/*定義棧*/,計算fun1(5)之值的過程如下： 將(5,*,1)進(jìn)棧; while (棧不空) if (棧頂元素未計算出棧頂元素的vf值即Sttop.tag=1) if (棧頂元素滿足(1)式) 求出對應(yīng)的Sttop.vf值,并置Sttop.tag=0; 表示已求出對應(yīng)的函數(shù)值; else /*棧頂元素滿足(2)式*/ 將(Sttop.vn-1,*,1)進(jìn)棧; else if (棧頂元素已計算出棧頂元素的vf值即Sttop.tag=0) 顯然棧頂元素由次棧頂元素通過(2)式分解得到的,回過來 由棧頂元素的vf值計算出次棧頂元素的vf值并退棧; if (棧

15、中只有一個已求出vf值的元素) 退出循環(huán); St0.vf即為所求的fun1(n)值;,求fun1(5)時棧St中元素的變化見教材p125圖6.2所示 。對應(yīng)的非遞歸fun1算法如下： int fun1(int n) top+; /*初值進(jìn)棧*/ Sttop.vn=n; Sttop.tag=1; while (top-1) /*棧不空時循環(huán)*/ if (Sttop.tag=1) /*未計算出棧頂元素的vf值*/ if (Sttop.vn=1)/*(1)式*/ Sttop.vf=1; Sttop.tag=0; else/*(2)式*/ top+; Sttop.vn=Sttop-1.vn-1; Sttop.ta