遞歸函數(shù)和非遞歸函數(shù)的轉變

1、第第6 6章章 遞歸遞歸 6.3 6.3 遞歸算法到非遞歸算法的轉換遞歸算法到非遞歸算法的轉換6.1 6.1 什么是遞歸什么是遞歸6.2 6.2 遞歸算法的設計遞歸算法的設計本章小結本章小結6.1 6.1 什么是遞歸什么是遞歸6.1.1 6.1.1 遞歸的定義遞歸的定義 在定義一個過程或函數(shù)時出現(xiàn)調(diào)用本過程或本在定義一個過程或函數(shù)時出現(xiàn)調(diào)用本過程或本函數(shù)的成分函數(shù)的成分, ,稱之為稱之為遞歸遞歸。若調(diào)用自身。若調(diào)用自身, ,稱之為稱之為直接直接遞歸遞歸。若過程或函數(shù)。若過程或函數(shù)p p調(diào)用過程或函數(shù)調(diào)用過程或函數(shù)q,q,而而q q又調(diào)用又調(diào)用p,p,稱之為稱之為間接遞歸間接遞歸。 例例 求求n

2、!(n為正整數(shù)為正整數(shù)) 。 一般的方法：一般的方法：n! = 1*2*(n-1)*n 遞歸的方法：遞歸的方法：時當時當 1 ,)!1( 0 , 1!nnnnn int factorial(int n) int x; if (n=0) x=1; else x=factorial (n-1)*n; return(x); 在該函數(shù)在該函數(shù)factorial (n)求解過程中求解過程中,直接調(diào)用直接調(diào)用factorial (n-1)自身自身,所以它是一個所以它是一個直接遞歸函數(shù)直接遞歸函數(shù)。 int factorial(int n) int x; if (n=0) x=1; else x=facto

3、rial (n-1)*n; return(x); n=4n=3n=2n=1n=06.1.2 6.1.2 何時使用遞歸何時使用遞歸 在以下三種情況下在以下三種情況下,常常要用到遞歸的方法。常常要用到遞歸的方法。 1. 定義定義是遞歸的是遞歸的 2. 數(shù)據(jù)結構數(shù)據(jù)結構是遞歸的是遞歸的 3. 問題的問題的求解方法求解方法是遞歸的是遞歸的 1. 定義是遞歸的定義是遞歸的 有許多有許多數(shù)學公式數(shù)學公式、數(shù)列數(shù)列等的定義是遞歸的。這些等的定義是遞歸的。這些問題的求解過程可以將其遞歸定義直接轉化為對應問題的求解過程可以將其遞歸定義直接轉化為對應的遞歸算法。的遞歸算法。 例如例如,求求Fibonacci數(shù)列數(shù)

4、列:1),2() 1(0,1,)(nnFibnFibnnnFib2. 數(shù)據(jù)結構是遞歸的數(shù)據(jù)結構是遞歸的 有些數(shù)據(jù)結構是遞歸的。例如有些數(shù)據(jù)結構是遞歸的。例如,第第2章中介紹過的單章中介紹過的單鏈表就是一種遞歸數(shù)據(jù)結構鏈表就是一種遞歸數(shù)據(jù)結構,其結點類型定義如下：其結點類型定義如下： typedef struct LNode ElemType data; struct LNode *next; LinkList; 對于遞歸數(shù)據(jù)結構對于遞歸數(shù)據(jù)結構,采用遞歸的方法編寫算法既方采用遞歸的方法編寫算法既方便又有效。例如便又有效。例如,求一個不帶頭結點的單鏈表求一個不帶頭結點的單鏈表head的所的所有有

5、data域域(假設為假設為int型型)之和的遞歸算法：之和的遞歸算法： int Sum(LinkList *head) if (head=NULL) return 0; else return (head-data+Sum(head-next); 3. 問題的求解方法是遞歸的問題的求解方法是遞歸的 有些問題的解法是遞歸的有些問題的解法是遞歸的,典型的有漢諾塔典型的有漢諾塔(Tower of Hanoi)問題求解：問題求解：盤片移動時必須遵守以下規(guī)則：盤片移動時必須遵守以下規(guī)則：每次只能移動一個盤片；每次只能移動一個盤片；盤片可以插在盤片可以插在A,B和和C中任一塔座；中任一塔座；不能將一個較大

6、的盤片放在較小的盤片上。不能將一個較大的盤片放在較小的盤片上。Hanoi(n,a,b,c)Hanoi(n-1,a,c,b)；move(n,a,c)；Hanoi(n-1,b,a,c)6.1.3 6.1.3 遞歸模型遞歸模型 遞歸模型是遞歸算法的抽象遞歸模型是遞歸算法的抽象,它反映遞歸問題的它反映遞歸問題的遞歸結構遞歸結構,例如例如,前面的遞歸算法對應的遞歸模型如下：前面的遞歸算法對應的遞歸模型如下：fun(0)=1 n=0(1) fun(n)=n*fun(n-1)n0 (2) 其中：第一個式子給出了其中：第一個式子給出了遞歸的終止條件遞歸的終止條件,我們稱我們稱之為之為遞歸出口遞歸出口；第二個式

7、子給出了；第二個式子給出了fun(n)的值與的值與fun(n-1)的值之間的關系，我們的值之間的關系，我們稱之為稱之為遞歸體遞歸體。 一般地一般地,一個遞歸模型是由一個遞歸模型是由遞歸出口遞歸出口和和遞歸體遞歸體兩部兩部分組成分組成, 前者確定前者確定遞歸到何時結束遞歸到何時結束, 后者確定后者確定遞歸求解遞歸求解時的遞推關系時的遞推關系。遞歸出口遞歸出口的一般格式如下：的一般格式如下： f(s1)=m1 (6.1) 這里的這里的s1與與m1均為常量均為常量,有些遞歸問題有些遞歸問題可能有幾個可能有幾個遞歸遞歸出口。出口。 遞歸體遞歸體的一般格式如下：的一般格式如下： f(sn+1)=g(f(

8、si),f(si+1),f(sn),cj,cj+1,cm) (6.2) 其中其中, n,i,j,m均為正整數(shù)。均為正整數(shù)。 sn+1是一個遞歸是一個遞歸“大問題大問題”, si,si+1,sn為遞歸為遞歸“小問題小問題”, cj,cj+1,cm是可以用非遞歸方法直接解決的問題是可以用非遞歸方法直接解決的問題 g是一個非遞歸函數(shù)是一個非遞歸函數(shù),可以直接求值。可以直接求值。遞歸思路遞歸思路 實際上實際上, 遞歸思路是把一個遞歸思路是把一個不能或不好直接求解不能或不好直接求解的的“大問題大問題”轉化成一個或幾個轉化成一個或幾個“小問題小問題”來解決來解決,再把這些再把這些“小問題小問題”進一步進一

9、步分解分解成更小的成更小的“小問題小問題”來解決來解決,如此分解如此分解,直至每個直至每個“小問題小問題”都可以直接解都可以直接解決決(此時此時分解到遞歸出口分解到遞歸出口)。 但遞歸分解不是隨意的分解但遞歸分解不是隨意的分解,遞歸分解遞歸分解要保證要保證“大大問題問題”與與“小問題小問題”相似相似,即求解過程與環(huán)境都相似。即求解過程與環(huán)境都相似。并且有一個并且有一個分解的終點分解的終點。從而使問題可解。從而使問題可解。 fun(5) d1:fun(4) d2:fun(3) d3:fun(2) d4:fun(1) 返回 1 fun(2)=2 fun(3)=6 fun(4)=24 fun(5)=

10、120 求解求解5!的過程如下：的過程如下：斐波那契數(shù)列的遞歸調(diào)用樹斐波那契數(shù)列的遞歸調(diào)用樹遞歸的執(zhí)行過程由遞歸的執(zhí)行過程由分解過程分解過程和和求值過程求值過程兩部分構成。兩部分構成。 分解過程分解過程是是“量變量變”過程過程,即原來的即原來的“大問題大問題”在慢慢在慢慢變小變小,但尚未解決；遇到遞歸出口后但尚未解決；遇到遞歸出口后,便發(fā)生了便發(fā)生了“質質變變”,即原遞歸問題便轉化成直接問題。即原遞歸問題便轉化成直接問題。6.2 6.2 遞歸算法的設計遞歸算法的設計 遞歸的求解的過程均有這樣的特征：先遞歸的求解的過程均有這樣的特征：先將整個問題將整個問題劃分為若干個子問題劃分為若干個子問題,通

11、過分別求解子問題通過分別求解子問題,最后獲得最后獲得整個問題的解。而這些整個問題的解。而這些子問題具有與原問題相同的求子問題具有與原問題相同的求解方法解方法,于是可以再將它們劃分成若干個子問題于是可以再將它們劃分成若干個子問題,分別分別求解求解,如此反復進行如此反復進行,直到不能再劃分成子問題直到不能再劃分成子問題,或已經(jīng)或已經(jīng)可以求解為止。這種自上而下將問題分解、求解可以求解為止。這種自上而下將問題分解、求解,再自再自上而下引用、合并上而下引用、合并,求出最后解答的過程稱為遞歸求解求出最后解答的過程稱為遞歸求解過程。這是一種過程。這是一種分而治之分而治之的算法設計方法。的算法設計方法。 遞歸

12、算法設計先要給出遞歸算法設計先要給出遞歸模型遞歸模型,再轉換成對應的再轉換成對應的C/C+語言函數(shù)。語言函數(shù)。 遞歸設計的步驟如下：遞歸設計的步驟如下： (1)對原問題對原問題f(s)進行分析進行分析,假設出合理的假設出合理的“較小問較小問題題”f(s)(與數(shù)學歸納法中假設與數(shù)學歸納法中假設n=k-1時等式成立相似時等式成立相似)； (2)假設假設f(s)是可解的是可解的,在此基礎上確定在此基礎上確定f(s)的解的解,即給出即給出f(s)與與f(s)之間的關系之間的關系(與數(shù)學歸納法中求證與數(shù)學歸納法中求證n=k時等式成時等式成立的過程相似立的過程相似)； (3)確定一個特定情況確定一個特定情

13、況(如如f(1)或或f(0)的解的解,由此作為由此作為遞遞歸出口歸出口(與數(shù)學歸納法中求證與數(shù)學歸納法中求證n=1時等式成立相似時等式成立相似)。 例如例如,采用遞歸算法求實數(shù)數(shù)組采用遞歸算法求實數(shù)數(shù)組A0.n-1中的最小值。中的最小值。 假設假設f(A,i)函數(shù)求數(shù)組元素函數(shù)求數(shù)組元素A0Ai中的最小值。中的最小值。 當當i=0時時,有有f(A,i)=A0； 假設假設f(A,i-1)已求出已求出,則則f(A,i)=MIN(f(A,i-1),Ai),其中其中MIN()為求兩個值較小值函數(shù)。因此得到如下遞歸模型：為求兩個值較小值函數(shù)。因此得到如下遞歸模型： A0 當當i=0時時 f(A,i)=

14、MIN(f(A,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 6.3 遞歸算法到非遞歸算法的轉換遞歸算法到非遞歸算法的轉換 遞歸算法有兩個基本特性：一是遞歸算法是一種分遞歸算法有兩個基本特性：一是遞歸算法是一種分而治之的、把復雜問題分解為簡單問題的求解問題方而治之的、把復雜問題分解為簡單問題的求解問題方法法,對求解某些復雜問題對求解某些復雜

15、問題,遞歸算法分析問題的方法是十遞歸算法分析問題的方法是十分分有效有效的；二是遞歸算法的的；二是遞歸算法的時間時間/空間效率通常比較差空間效率通常比較差。 因此因此,對求解某些問題時對求解某些問題時,我們希望我們希望用遞歸算法分析用遞歸算法分析問題問題,用非遞歸算法具體求解問題用非遞歸算法具體求解問題。這就需要把遞歸算。這就需要把遞歸算法轉換為非遞歸算法。法轉換為非遞歸算法。把遞歸算法轉化為非遞歸算法有如下三種基本方法：把遞歸算法轉化為非遞歸算法有如下三種基本方法： (1)通過分析，跳過通過分析，跳過分解過程分解過程，直接用，直接用循環(huán)結構循環(huán)結構的算的算法實現(xiàn)法實現(xiàn)求值過程求值過程。 (2)

16、自己用自己用棧棧模擬系統(tǒng)的運行時棧模擬系統(tǒng)的運行時棧,通過分析只保存必通過分析只保存必須保存的信息須保存的信息,從而用非遞歸算法替代遞歸算法。從而用非遞歸算法替代遞歸算法。 (3)利用利用棧棧保存參數(shù)保存參數(shù),由于棧的后進先出特性吻合遞歸由于棧的后進先出特性吻合遞歸算法的執(zhí)行過程算法的執(zhí)行過程,因而可以用非遞歸算法替代遞歸算法。因而可以用非遞歸算法替代遞歸算法。6.3.1 6.3.1 利用循環(huán)跳過分解過程從而消除遞歸利用循環(huán)跳過分解過程從而消除遞歸 采用循環(huán)結構消除遞歸。求解采用循環(huán)結構消除遞歸。求解Fibonacci數(shù)列的算數(shù)列的算法如下：法如下： int Fib(int n) int i,

17、f1,f2,f3; if (n=1 | n=2) return(n); f1=1;f2=2; for (i=3;i-1) /*棧不空時循環(huán)棧不空時循環(huán)*/ if (Sttop.tag=1) /*未計算出棧頂元素的未計算出棧頂元素的vf值值*/ if (Sttop.vn=0)/*(1)式式*/ Sttop.vf=1; Sttop.tag=0; else/*(2)式式*/ top+; Sttop.vn=Sttop-1.vn-1; Sttop.tag=1; else if (Sttop.tag=0) /*已計算出已計算出vf值值*/ Sttop-1.vf=Sttop-1.vn*Sttop.vf; /*(2)式式*/ Sttop-1.tag=0; top-; /*棧中只有一個已求