遞歸與非遞歸程序的轉(zhuǎn)換

1、遞歸程序非遞歸程序10 遞歸的基本概念遞歸：在定義一個(gè)過(guò)程或函數(shù)時(shí)，如果出現(xiàn)調(diào)用本過(guò)程或本函數(shù)的成分，則稱為遞歸。直接遞歸：在定義一個(gè)過(guò)程或函數(shù)時(shí)，出現(xiàn)直接調(diào)用本過(guò)程或本函數(shù)成分的情況。直接遞歸：在定義一個(gè)過(guò)程或函數(shù)時(shí)，出現(xiàn)間接調(diào)用本過(guò)程或本函數(shù)成分的情況。20 遞歸的基本概念function_1(X) if( X) X*function_1(X-1); else return;Function_1、function_2實(shí)現(xiàn)了什么功能？還有哪些常見(jiàn)的遞歸函數(shù)？function_2(X) if( X) function_3(X); else return;function_3(X) return

2、 X*function_2(X-1);30 遞歸的基本概念在什么情況下用到遞歸方法給出的定義是遞歸的：許多數(shù)學(xué)公式、數(shù)列的定義是遞歸的，這是可以直接把遞歸定義轉(zhuǎn)換為遞歸算法：例如Fabonacci數(shù)列。數(shù)據(jù)結(jié)構(gòu)是遞歸的：常見(jiàn)的有樹、鏈表等數(shù)據(jù)結(jié)構(gòu)的定義。對(duì)于這類數(shù)據(jù)結(jié)構(gòu)，常采用遞歸的方法進(jìn)行操作。例如鏈表的遍歷、樹的遍歷操作。問(wèn)題求解的方法是遞歸的。例如漢諾塔問(wèn)題，其求解方法是遞歸的。41 遞歸算法的設(shè)計(jì)遞歸模型：遞歸模型是遞歸算法的抽象,它反映遞歸問(wèn)題的遞歸結(jié)構(gòu),例如,前面的遞歸算法對(duì)應(yīng)的遞歸模型如下：fun(0)=1 n=0(1) fun(n)=n*fun(n-1)n0(2) 其中：第一個(gè)

3、式子給出了遞歸的終止條件,我們稱之為遞歸出口；第二個(gè)式子給出了fun(n)的值與fun(n-1)的值之間的關(guān)系，我們稱之為遞歸體。51 遞歸算法的設(shè)計(jì)一般地,一個(gè)遞歸模型是由遞歸出口和遞歸體兩部分組成, 前者確定遞歸到何時(shí)結(jié)束, 后者確定遞歸求解時(shí)的遞推關(guān)系。遞歸出口的一般格式如下： f(s1)=m1這里的s1與m1均為常量,有些遞歸問(wèn)題可能有幾個(gè)遞歸出口。61 遞歸算法的設(shè)計(jì)遞歸體的一般格式如下： f(sn+1)=g(f(si),f(si+1),f(sn),cj,cj+1,cm) 其中, n,i,j,m均為正整數(shù)。 sn+1是一個(gè)遞歸“大問(wèn)題”, si,si+1,sn為遞歸“小問(wèn)題”, cj

4、,cj+1,cm是可以用非遞歸方法直接解決的問(wèn)題 g是一個(gè)非遞歸函數(shù),可以直接求值。71 遞歸算法的設(shè)計(jì)遞歸思路實(shí)際上，遞歸思路是把一個(gè)不能或不好直接求解的“大問(wèn)題”轉(zhuǎn)化成一個(gè)或幾個(gè)“小問(wèn)題”來(lái)解決，再把這些“小問(wèn)題”進(jìn)一步分解成更小的“小問(wèn)題”來(lái)解決，如此分解，直至每個(gè)“小問(wèn)題”都可以直接解決(此時(shí)分解到遞歸出口)。但遞歸分解不是隨意的分解，遞歸分解要保證“大問(wèn)題”與“小問(wèn)題”相似，即求解過(guò)程與環(huán)境都相似。并且有一個(gè)分解的終點(diǎn)。從而使問(wèn)題可解。 81 遞歸算法的設(shè)計(jì)逐步分解和組合求值的過(guò)程91 遞歸算法的設(shè)計(jì)斐波那契數(shù)：一個(gè)大問(wèn)題分解為多個(gè)小問(wèn)題的過(guò)程101 遞歸算法的設(shè)計(jì)算法設(shè)計(jì)：先將整個(gè)

5、問(wèn)題劃分為若干個(gè)子問(wèn)題，通過(guò)分別求解子問(wèn)題，最后獲得整個(gè)問(wèn)題的解。而這些子問(wèn)題具有與原問(wèn)題相同的求解方法，于是可以再將它們劃分成若干個(gè)子問(wèn)題，分別求解，如此反復(fù)進(jìn)行，直到不能再劃分成子問(wèn)題，或已經(jīng)可以求解為止。這種自上而下將問(wèn)題分解、求解，再自上而下引用、合并，求出最后解答的過(guò)程稱為遞歸求解過(guò)程。這是一種分而治之的算法設(shè)計(jì)方法。111 遞歸算法的設(shè)計(jì)遞歸設(shè)計(jì)的步驟如下：(1)對(duì)原問(wèn)題f(s)進(jìn)行分析,假設(shè)出合理的“較小問(wèn)題”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

6、時(shí)等式成立的過(guò)程相似)；(3)確定一個(gè)特定情況(如f(1)或f(0)的解,由此作為遞歸出口(與數(shù)學(xué)歸納法中求證n=1時(shí)等式成立相似)。121 遞歸算法的設(shè)計(jì)課堂練習(xí)：采用遞歸算法求實(shí)數(shù)數(shù)組A0.n-1中的最小值?；静襟E：先定義清楚問(wèn)題；寫出遞歸模型；轉(zhuǎn)換為算法。132 為什么：遞歸非遞歸？引例求如下函數(shù)值 Sum(1.X)=X+Sum(1.X-1) X0 Sum(1.X)=0 X=0它的程序？ 142 為什么：遞歸非遞歸？利用遞歸求該函數(shù)#include stdafx.h#include using namespace std;int _tmain(int argc, _TCHAR* arg

7、v)coutadd(5000);return 0;int add(int x)if(x=0) return 0;return x+add(x-1);152 為什么：遞歸非遞歸？利用非遞歸(迭代)求該函數(shù)#include stdafx.h#include using namespace std;int _tmain(int argc, _TCHAR* argv)cout0; i-)result+=x;return result;162 為什么：遞歸非遞歸？它們的運(yùn)行結(jié)果？ 遞歸 迭代X=10 X=100X=1000X=10000X=100000 為什么？172 為什么：遞歸非遞歸？利用遞歸求該函

8、數(shù)#include stdafx.h#include using namespace std;int _tmain(int argc, _TCHAR* argv)coutadd(5000);return 0;int add(int x) char a1000;if(x=224討論直接使用棧保存中間結(jié)果，從而將遞歸算法轉(zhuǎn)化為非遞歸算法的過(guò)程。以求N!為例,其遞歸模型有一個(gè)遞歸體和一個(gè)遞歸出口兩個(gè)式子,分別稱為(1)式和(2)式。3 遞歸非遞歸的轉(zhuǎn)換方法1-表述225設(shè)計(jì)一個(gè)棧,其結(jié)構(gòu)如下： struct int vn; /*保存n值*/int vf; /*保存fun1(n)值*/int tag;

9、 /*標(biāo)識(shí)是否求出fun1(n)值,1:未求出,0:已求出*/ StMaxSize;/*定義簡(jiǎn)單數(shù)組棧*/ 3 遞歸非遞歸的轉(zhuǎn)換方法1-表述226計(jì)算fun1(5)之值的過(guò)程如下：將(5,*,1)進(jìn)棧;while (棧不空) if (未計(jì)算出棧頂元素的vf值即Sttop.tag=1) if (棧頂元素滿足(1)式) 求出對(duì)應(yīng)的Sttop.vf值, 置Sttop.tag=0;else /*棧頂元素滿足(2)式*/ 將(Sttop.vn-1,*,1)進(jìn)棧; else if (已計(jì)算出棧頂元素的vf值即Sttop.tag=0) 顯然棧頂元素由次棧頂元素通過(guò)(2)式分解得到的，回過(guò)來(lái) 由棧頂元素的vf

10、值計(jì)算出次棧頂元素的vf值并退棧; if (棧中只有一個(gè)已求出vf值的元素) 退出循環(huán);St0.vf即為所求的fun1(n)值; 3 遞歸非遞歸的轉(zhuǎn)換方法1-表述2273 遞歸非遞歸的轉(zhuǎn)換方法1-表述2 對(duì)應(yīng)的非遞歸fun1算法如下： int fun1(int n) top+; /*初值進(jìn)棧*/ Sttop.vn=n; Sttop.tag=1; while (top-1) /*棧不空時(shí)循環(huán)*/ if (Sttop.tag=1) /*未計(jì)算出棧頂元素的vf值*/ if (Sttop.vn=0)/*(1)式*/ Sttop.vf=1; Sttop.tag=0; else/*(2)式*/ top+;

11、 Sttop.vn=Sttop-1.vn-1; Sttop.tag=1; 283 遞歸非遞歸的轉(zhuǎn)換方法1-表述2else if (Sttop.tag=0) /*已計(jì)算出vf值*/ Sttop-1.vf=Sttop-1.vn*Sttop.vf; /*(2)式*/ Sttop-1.tag=0; top-; /*棧中只有一個(gè)已求出vf的元素時(shí)退出循環(huán)*/ if (top=0 & Sttop.tag=0) break;return(Sttop.vf); 293 遞歸非遞歸的轉(zhuǎn)換方法1-表述2練習(xí)以N=5為例，完整的在紙上模擬整個(gè)算法的運(yùn)算過(guò)程，以此加深對(duì)表述2的理解。以表述2方法，求斐波那契數(shù)的棧模擬

12、遞歸算法。其中，斐波那契數(shù)（Fobanacci）定義如下：f(1)=1f(2)=1f(n)=f(n-1)+f(n-2),其中n=2303 遞歸非遞歸的轉(zhuǎn)換方法2利用棧保存參數(shù)：該方法通常以棧為保存運(yùn)行中間數(shù)據(jù)的媒介。例：二叉樹的中序遍歷。DFS( T )DFS(T-lchild);Visit( T );DFS(T-rchild);313 遞歸非遞歸的轉(zhuǎn)換方法2Status InOrder(BiTree root, Status(* Visit)(ElemType e) /*中序遍歷二叉樹, root指向二叉樹(或某一子樹) */ if (root! =NULL) if( InOrder(roo

13、t -LChild, visit) /*遍歷左子樹*/ if(Visit(root -data) /*訪問(wèn)根結(jié)點(diǎn)*/ if(InOrder(root -RChild , visit) /*遍歷右子樹*/ return OK;return Error; else return OK; 323 遞歸非遞歸的轉(zhuǎn)換方法2利用棧來(lái)模擬整個(gè)遍歷過(guò)程，再根據(jù)遍歷寫出算法。333 遞歸非遞歸的轉(zhuǎn)換方法2void InOrder（BiTree root）/* 中序遍歷二叉樹的非遞歸算法 */ InitStack (S); p=root; while(p! =NULL | !IsEmpty(S) if (p! =

14、NULL) /* 根指針進(jìn)棧， 遍歷左子樹 */ Push(S, p); p=p-LChild; else /*根指針退棧， 訪問(wèn)根結(jié)點(diǎn)， 遍歷右子樹*/ Pop(S, p); Visit(p-data); p=p-RChild; /end of while 343 遞歸非遞歸的轉(zhuǎn)換方法3利用迭代消除遞歸：通過(guò)分析，跳過(guò)分解過(guò)程，直接用循環(huán)結(jié)構(gòu)的算法實(shí)現(xiàn)求值過(guò)程。斐波那契數(shù)（Fobanacci）定義如下：f(1)=1f(2)=1f(n)=f(n-1)+f(n-2),其中n=2從中找出循環(huán)求值。353 遞歸非遞歸的轉(zhuǎn)換方法3求解Fibonacci數(shù)列的算法如下： int Fib(int n) i

15、nt 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); 363 遞歸非遞歸的轉(zhuǎn)換方法3利用迭代求解的難點(diǎn)：要很好地理解整個(gè)算法的思想，然后重新設(shè)計(jì)一個(gè)合理的迭代過(guò)程。370-1背包問(wèn)題 0-1背包問(wèn)題：給定n種物品和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問(wèn)應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?0-1背包問(wèn)題是一個(gè)特殊的整數(shù)規(guī)劃問(wèn)題。價(jià)值 體積3 遞歸非遞歸的轉(zhuǎn)換方法338建立模型分析：定義m(i，j)是背包容量為j，可選擇物品為i，i+1，n時(shí)0-1背包問(wèn)題的最優(yōu)值。可以建立計(jì)算m(i，j)的遞