遞歸算法詳解.doc

_遞歸馮文科一、遞歸的基本概念。一個(gè)函數(shù)、概念或數(shù)學(xué)結(jié)構(gòu)，如果在其定義或說明內(nèi)部直接或間接地出現(xiàn)對(duì)其本身的引用，或者是為了描述問題的某一狀態(tài)，必須要用至它的上一狀態(tài)，而描述上一狀態(tài)，又必須用到它的上一狀態(tài)這種用自己來定義自己的方法，稱之為遞歸或遞歸定義。在程序設(shè)計(jì)中，函數(shù)直接或間接調(diào)用自己，就被稱為遞歸調(diào)用。二、遞歸的最簡(jiǎn)單應(yīng)用：通過各項(xiàng)關(guān)系及初值求數(shù)列的某一項(xiàng)。在數(shù)學(xué)中，有這樣一種數(shù)列，很難求出它的通項(xiàng)公式，但數(shù)列中各項(xiàng)間關(guān)系卻很簡(jiǎn)單，于是人們想出另一種辦法來描述這種數(shù)列：通過初值及與前面臨近幾項(xiàng)之間的關(guān)系。要使用這樣的描述方式，至少要提供兩個(gè)信息：一是最前面幾項(xiàng)的數(shù)值，一是數(shù)列間各項(xiàng)的關(guān)系。比如階乘數(shù)列1、2、6、24、120、720如果用上面的方式來描述它，應(yīng)該是：如果需要寫一個(gè)函數(shù)來求的值，那么可以很容易地寫成這樣：int f(int n)if(n=1)return 1; return n*f(n-1);這就是遞歸函數(shù)的最簡(jiǎn)單形式，從中可以明顯看出遞歸函數(shù)都有的一個(gè)特點(diǎn)：先處理一些特殊情況這也是遞歸函數(shù)的第一個(gè)出口，再處理遞歸關(guān)系這形成遞歸函數(shù)的第二個(gè)出口。遞歸函數(shù)的執(zhí)行過程總是先通過遞歸關(guān)系不斷地縮小問題的規(guī)模，直到簡(jiǎn)單到可以作為特殊情況處理而得出直接的結(jié)果，再通過遞歸關(guān)系逐層返回到原來的數(shù)據(jù)規(guī)模，最終得出問題的解。以上面求階乘數(shù)列的函數(shù)為例。如在求時(shí)，由于3不是特殊值，因此需要計(jì)算，但是對(duì)它自己的調(diào)用，于是再計(jì)算，2也不是特殊值，需要計(jì)算，需要知道的值，再計(jì)算，1是特殊值，于是直接得出，返回上一步，得，再返回上一步，得，從而得最終解。用圖解來說明，就是的執(zhí)行過程（特殊值判斷：），繼續(xù)向下。（遞歸關(guān)系處理：）求，需要先計(jì)算，調(diào)用，且本身掛起得到，由正常出口返回的執(zhí)行過程（特殊值判斷：），繼續(xù)向下。（遞歸關(guān)系處理：）求，需要先計(jì)算，調(diào)用，且本身掛起得到，由正常出口返回的執(zhí)行過程（特殊值判斷：），由特殊情況出口直接返回1。下面再看一個(gè)稍復(fù)雜點(diǎn)的例子?！纠?】數(shù)列的前幾項(xiàng)為1、輸入，編程求的精確分?jǐn)?shù)解。分析：這個(gè)題目較易，發(fā)現(xiàn)，其它情況下有。如要求實(shí)數(shù)解的話，這基本已經(jīng)可以寫出遞歸函數(shù)了。但由于題目要求精確的分?jǐn)?shù)解，還需做一些調(diào)整。設(shè)，則由遞歸關(guān)系，有，再約分化簡(jiǎn)，即得。但發(fā)現(xiàn)一個(gè)問題：求出時(shí)，需要返回兩個(gè)整數(shù)：分子與分母，而通常的函數(shù)只能返回一個(gè)整數(shù)。這個(gè)問題一般有兩類解決辦法，一種是讓求值函數(shù)返回一個(gè)結(jié)構(gòu)體變量，這樣就可以返回兩個(gè)變量了（其實(shí)還可以不只兩個(gè)呢）；另一種是在求值函數(shù)的參數(shù)表中加入兩個(gè)指針變量或引用變量，通過參數(shù)給帶回?cái)?shù)值。但由于后一種做法會(huì)使程序結(jié)構(gòu)不清晰返回值是由參數(shù)表得到的，因此我們使用前一種方法。另外，在通過得出后，就已經(jīng)是最簡(jiǎn)分?jǐn)?shù)了，無須化簡(jiǎn)。證明如下：若是最簡(jiǎn)分?jǐn)?shù)，即說明的最大公約數(shù)為1，即對(duì)任何，都有與不全為0，不防記、，則有只要與不全為0，且，就有與不全為0。因此對(duì)任何的，有與不全為0。而對(duì)于的情況而言，記，則有由于，因此同樣有與不全為0。所以對(duì)任意，都有與不全為0，因此它們的最大公約數(shù)為1，即是最簡(jiǎn)分?jǐn)?shù)。雖然這是個(gè)要求（即）是最簡(jiǎn)分?jǐn)?shù)的結(jié)論，但由于數(shù)列第二項(xiàng)為，是最簡(jiǎn)分?jǐn)?shù)，因此可以證明第三項(xiàng)也是最簡(jiǎn)分?jǐn)?shù)，同時(shí)也證明對(duì)所有的，求出的就是最簡(jiǎn)分?jǐn)?shù)，無須化簡(jiǎn)。具體代碼如下：/ Exam1.cpp#include using namespace std;struct FS unsigned long long q, p;FS f(int n) FS r; if(n=1) r.q=1; r.p=1; return r; r=f(n-1); r.p=r.p+r.q; r.q=r.p-r.q; return r;int main() FS r; int n; cinn; r=f(n); coutr.q/r.pendl; system(pause); return 0;三、遞歸的精髓：只考慮當(dāng)前一步，剩下的讓下一步去做吧。對(duì)大多數(shù)問題而言，當(dāng)它的規(guī)模縮小至“特殊情況”時(shí)，都可以非常輕易地得出問題的解，因此我們不過多地討論“特殊情況”，只詳細(xì)地討論遞歸關(guān)系的確定。尋找遞歸關(guān)系，最低標(biāo)準(zhǔn)是它能使問題的規(guī)模變小，且變小后的問題與原問題在本質(zhì)上是一樣的。當(dāng)找到遞歸關(guān)系后，我們的遞歸函數(shù)只須處理特殊情況與遞歸關(guān)系，不需要處理其它的信息至于下一步的事情，就讓下一步去做吧。另一個(gè)需要考慮的事情就是遞歸函數(shù)的參數(shù)表，首先，在通常情況下，參數(shù)表都要使用變量參數(shù)，且遞歸函數(shù)中盡量使用局部變量這會(huì)減少很多不必要的麻煩；其次，參數(shù)表中，大多都有一個(gè)表示當(dāng)前在執(zhí)行第幾步的參數(shù)?！纠?】下圖是一個(gè)有向圖，輸入，打印的所有路徑。1357902468分析：仔細(xì)研究這個(gè)圖的特點(diǎn)，發(fā)現(xiàn)以下規(guī)律：對(duì)任何結(jié)點(diǎn)，都可以走到和，當(dāng)然如果它們不超過9的話。由于要打印路徑，因此需要保存查找過程中的部分路徑信息?？梢宰鲆粋€(gè)全局?jǐn)?shù)組path來存儲(chǔ)這個(gè)信息，由于結(jié)點(diǎn)0沒有來路，且是所有路徑的起點(diǎn)，因此記path0=0，遞歸函數(shù)負(fù)責(zé)填寫之后的路徑結(jié)點(diǎn)。我們這樣設(shè)計(jì)遞歸函數(shù)：首先，這個(gè)遞歸函數(shù)的參數(shù)表中至少需要一個(gè)參數(shù)i，它的意義是表示現(xiàn)在在填路徑中的第幾個(gè)結(jié)點(diǎn)，而pathi可以填的數(shù)，要么是上一個(gè)結(jié)點(diǎn)加1，要么是上一個(gè)結(jié)點(diǎn)加2，即pathi=pathi-1+1或pathi=pathi-1+2；其次，特殊情況的討論：我們要找的是終止到的路徑，因此若出現(xiàn)pathi-1=的情況，就說明已經(jīng)找到路徑，無須將當(dāng)前層再填入結(jié)點(diǎn)，可以將path中的信息輸出并結(jié)束函數(shù)了這是遞歸函數(shù)的特殊情況出口；第三、遞歸關(guān)系的處理：若還沒到達(dá)結(jié)點(diǎn)，則填寫本結(jié)點(diǎn)pathi，上文已說明，pathi=pathi-1+1或pathi=pathi-1+2，當(dāng)然如果它們都不過9的話。將結(jié)點(diǎn)填好后，說明路徑向下走了一步，距離結(jié)點(diǎn)更近了一步，問題規(guī)模已經(jīng)變小。不要處理其它東西，直接遞歸，通過遞歸調(diào)用去填寫i+1結(jié)點(diǎn)就可以了。這里有處和【例1】不相同的地方，即pathi是有兩種可能可選的，我們的處理這這樣的，先令pathi=pathi-1+1，然后遞歸調(diào)用，填寫i+1結(jié)點(diǎn)，當(dāng)這個(gè)調(diào)用返回時(shí)，說明所有pathi為pathi-1+1的路徑都已經(jīng)討論完成了，再令pathi=pathi-1+2，再遞歸，當(dāng)它返回時(shí)，整個(gè)函數(shù)執(zhí)行完畢，形成正常的執(zhí)行完成時(shí)的出口。具體代碼如下：/ Exam2.cpp#include using namespace std;#define MAX 9int pathMAX, N;int write(int i) int j; for(j=0;ji;j+) coutpathj; coutpathiendl;void f(int i) if(pathi-1=N) write(i-1); return; if(pathi-1+1=N) pathi=pathi-1+1; f(i+1); if(pathi-1+2N; path0=0; f(1); system(pause); return 0;【例3】我的畫筆。Windows中的畫筆從Windows3.x時(shí)代開始就已經(jīng)有了，雖然功能與Photoshop不能相比，但它小巧而迅速，一般的簡(jiǎn)單功能還是很方便的。畫筆中的填色工具是油漆桶，選定它，再指定一個(gè)顏色，在圖片中一點(diǎn)，所有與這個(gè)點(diǎn)顏色相同且相連的象素就都被填充了。如下圖示：畫筆的油漆桶工具填充的是一個(gè)叫“四連通”的區(qū)域，即它只從上、下、左、右四個(gè)方向向外擴(kuò)展。請(qǐng)編寫程序，模擬油漆通工具。輸入文件：Exam3In.txt中有10行，每行是一個(gè)10字符的字符串，表示一個(gè)10*10的圖象，不同的字符表示不同的顏色；之后的一行有兩個(gè)用空格分開的整數(shù)，表示油漆桶點(diǎn)中的位置，再后面一行是一個(gè)字符，表示油漆桶的填充顏色。輸出文件：Exam3Out.txt，輸出10行，每行10個(gè)字符的字符串，表示填充后的圖象。分析：本題給了一個(gè)點(diǎn)的位置，查找所有與它“四連通”的點(diǎn)就成為本題的核心問題。我們的算法是這樣的：先從這個(gè)起點(diǎn)出發(fā)，沿四個(gè)方向展開，看這“直接相連”的四個(gè)點(diǎn)是否可以填充，若有可以的，則再以這個(gè)點(diǎn)為中心，再向四個(gè)方向展開直到所有可能展開的點(diǎn)都不能再展開了為止。遞歸函數(shù)這樣設(shè)計(jì)：首先它的參數(shù)表需要兩個(gè)參數(shù)，表示本次從哪個(gè)位置點(diǎn)展開；其次，依次討論它四個(gè)方向上相鄰的點(diǎn)是否可填充與起點(diǎn)顏色相同，如果可以，則填充，并以此點(diǎn)為中心，遞歸調(diào)用。代碼如下：/ Exam3.cpp#include using namespace std;#define N 10ifstream fin(Exam3In.txt);ofstream fout(Exam3Out.txt);char picNN+1, c, p;int col, row;void fill(int i, int j) if(i-1=0 & pici-1j=p) pici-1j=c; fill(i-1, j); if(i+1=0 & picij-1=p) picij-1=c; fill(i, j-1); if(j+1N & picij+1=p) picij+1=c; fill(i, j+1); int main() int i; for(i=0;ipici; finrowcol; finc; p=picrowcol; picrowcol=c; fill(row, col); for(i=0;iN;i+) foutpiciendl; return 0;本題中的遞歸函數(shù)fill似乎與常規(guī)的遞歸函數(shù)比較起來缺少了處理特殊情況的部分，其實(shí)不然，它的特殊情況處理已經(jīng)被融合到遞歸關(guān)系的處理當(dāng)中了，正常與非正常的出口合并到一起。特殊情況就是：當(dāng)向四個(gè)方向都無法展開時(shí)，程序直接退出。這個(gè)程序的fill函數(shù)運(yùn)用的算法就是“種子填充算法”的遞歸寫法。它另有動(dòng)態(tài)規(guī)劃的寫法當(dāng)然比這個(gè)要快得多，大家可以想一想如何實(shí)現(xiàn)。四、遞歸函數(shù)的必然用法：處理遞歸定義的數(shù)據(jù)結(jié)構(gòu)。一些常用的數(shù)據(jù)結(jié)構(gòu)本身就是遞歸定義的，寫一個(gè)遞歸的函數(shù)來處理它，當(dāng)然是再正常不過的事情，就比如說二叉樹、廣義表【例4】二叉樹的操作。用字符串的形式給定一個(gè)完全二叉樹，保存在輸入文件Exam4In.txt中，編寫程序輸出其后序遍歷的結(jié)果至輸出文件Exam4Out.txt中。分析：本題的程序是簡(jiǎn)單的，唯一要注意的是：C+的數(shù)組從下標(biāo)0開始，因此對(duì)于結(jié)點(diǎn),它的左孩子編號(hào)應(yīng)該是，右孩子編號(hào)應(yīng)該是。其它的地方?jīng)]什么難度。代碼如下：/ Exam4.cpp#include using namespace std;#define M 100ifstream fin(Exam4In.txt);ofstream fout(Exam4Out.txt);char treeM;int L;void run(int i) if(2*i+1L) run(2*i+1); if(2*(i+1)L) run(2*(i+1); fouttree; L=strlen(tree); run(0); return 0;【例5】以字符串形式給出一棵完全二叉樹的先序遍歷與中序遍歷序列，編程輸出用字符串形式表示的完全二叉樹的結(jié)構(gòu)。分析：先序遍歷的首結(jié)點(diǎn)一定是整棵樹的根，因此可以直接標(biāo)在0處。在中序遍歷序列中，它左邊的結(jié)點(diǎn)構(gòu)成左子樹，右邊的結(jié)點(diǎn)構(gòu)成右子樹，從而可以知道，左子樹與右子樹的結(jié)點(diǎn)個(gè)數(shù)，進(jìn)而得到及左子樹與右子樹的先序遍歷與中序遍歷序列，遞歸查找所有子樹的根即可。為了得到整棵樹的結(jié)構(gòu)，設(shè)置全局?jǐn)?shù)組tree來存儲(chǔ)，全局?jǐn)?shù)組s的意義是：si存儲(chǔ)整數(shù)表示第i層結(jié)點(diǎn)的起始下標(biāo)。代碼如下：/ Exam5.cpp#include using namespace std;#define M 100ifstream fin(Exam5In.txt);ofstream fout(Exam5Out.txt);char preM, midM, treeM;int L, sM;void build(int layer, int ps, int pe, int ms, int me) treeslayer=preps; slayer+; if(ps=pe) return; int i; i=ms; while(midi!=preps) i+; build(layer+1, ps+1, ps+i-ms, ms, i-1); build(layer+1, ps+i-ms+1, pe, i+1, me);int main() finpremid; L=strlen(pre); s0=0; int i, j; i=1; j=2; while(siL) si=j-1; j=j*2; i+; build(0, 0, L-1, 0, L-1); treeL=0; fouttree; return 0;五、遞歸與回溯法。遞歸的另一個(gè)常用的地方是實(shí)現(xiàn)回溯法。所謂回溯法，一般就是指先將問題分成幾步，在每一步時(shí)嘗試所有的可能，直到達(dá)到最終要求，或最后一步將所有可能嘗試完成后，再回到上一步，使上一步嘗試下一種可能，并繼續(xù)的作法。由于回溯的“步驟性”明顯，因此用遞歸實(shí)現(xiàn)回溯是相當(dāng)方便的事?？聪旅娴囊粋€(gè)例題：【例6】n皇后問題。輸入整數(shù)n，打印n皇后問題的所有解及解的總數(shù)。代碼如下：/ Exam6.cpp#include using namespace std;#define MAX 100int n, qMAX, c;bool markMAX;void write() int i; char tMAX; memset(t, ., MAX*sizeof(char); tn=0; for(i=0;in;i+) tqi=Q; couttendl; tqi=.; coutendl;bool test(int i, int k) int j; j=0; while(jk & abs(j-k)!=abs(qj-i) j+; if(j=k & marki=false) return true; else return false;void search(int k) if(k=n) write(); c+; return; int i; for(i=0;in; memset(mark, 0, MAX*sizeof(bool); c=0; search(0); coutcendl; system(pause); return 0;六、練習(xí)【練習(xí)】為給定的表達(dá)式建立表達(dá)式樹，并求值。給定的表達(dá)式中，所有數(shù)字都是1位正整數(shù)，出現(xiàn)的符號(hào)可能為、*、/、（、）。分析：這是一個(gè)與一般數(shù)據(jù)結(jié)構(gòu)書上講的用棧計(jì)算的方法本質(zhì)不同的方法。在詳細(xì)說明這個(gè)算法之前，需要首先明確這個(gè)算法用到的概念1、單元：一個(gè)單元可能是用括號(hào)括起來的一個(gè)表達(dá)式，或是一個(gè)整數(shù)；2、項(xiàng)：一個(gè)項(xiàng)是指由*與/連接起來的若干單元；3、表達(dá)式：一個(gè)表達(dá)式是指由或連接起來的若干項(xiàng)。要建立表達(dá)式樹，需要三個(gè)函數(shù)互相調(diào)用的函數(shù)：一個(gè)是getunit，用于建立一個(gè)單元；一個(gè)是getexpr，用于建立一個(gè)項(xiàng)，另一個(gè)就是build，用于建立一個(gè)表達(dá)式。getunit函數(shù)較易，如果字符串首字母是（的話，那么從它后面的字符開始用build建立一個(gè)表達(dá)式，這個(gè)表達(dá)式就是一個(gè)單元；否則，就處理一個(gè)整數(shù)；getexpr函數(shù)是建立在getunit之上的，它先用getunit建立一個(gè)單元，然后不停地考察之后地連接符號(hào)是不是*或/，若是，則不停地重復(fù)讀連接符、建立另一個(gè)單元、建立連接的操作，直到連接符號(hào)不是*或/為止。build函數(shù)是用于最終建立表達(dá)式的，它先用getexpr建立一個(gè)項(xiàng)，再用符號(hào)將剩余的各項(xiàng)連接成二叉樹。代碼如下：/ Exer.cpp#include using namespace std;struct NODE int n; char c; NODE *left, *right; NODE() left=NULL; right=NULL; ;char s100;int cur;NODE *tree;void clear(NODE *root) if(root=NULL) return; clear(root-left); clear(root-right); delete root;void cal(NODE *root) if(root-left!=NULL) cal(root-left); cal(root-right); switch(root-c) case +: root-n=root-left-n+root-right-n; break; case -: root-n=root-left-n-root-right-n; break; case *: root-n=root-left-n*root-right-n; break; case /: root-n=root-left-n/root-right-n; NODE *build();NODE *getunit() NODE *a; if(scur=() cur+; a=build(); else a=new NODE; a-n=scur-0; cur+; return a;NODE *getexpr() NODE *a, *b, *c; a=getunit(); while(scur=* | scur=/) b=new NODE; b-c=scur; cur+; c=getunit(); b-left=a; b-right=c; a=b; return a;NODE *build() NODE *a, *b, *c; a=getexpr(); while(scur!=0 & scur!=) b=new NODE; b-c=scur; cur+; c=getexpr(); b-left=a; b-right=c; a=b; if(scur=) cur+; return a;int main() cins; cur=0; tree=build(); cal(tree); coutn0又例如，F(xiàn)ibonacci(斐波那契)數(shù)列可遞歸定義為 0 若n=0Fib(n) = 1 若n=1 Fib(n-1)+Fib(n-2) 若n1 據(jù)此可以寫出實(shí)現(xiàn)求n 的階乘和求Fibonacci數(shù)列中第n項(xiàng)的遞歸算法，如算法21和算法22所示。long int fact(int n) /求非負(fù)整數(shù)n的階乘if(!n) return 1; /0!=1else return n*fact(n-1); /n!=n*(n-1)!/fact算法21 求階乘的遞歸算法long int fib(int n) /求斐波那契數(shù)列中的第n個(gè)數(shù)if(n1,f(n)=f(n-1)+f(n-2)/fib算法22 求斐波那契數(shù)的遞歸算法 一般地說，每一個(gè)遞歸函數(shù)的定義都包含兩個(gè)部分。(1) 遞歸基礎(chǔ) 對(duì)無需遞歸的規(guī)模最小的問題直接進(jìn)行處理。(2) 遞歸步驟 將一般情況的問題簡(jiǎn)化成一個(gè)或多個(gè)規(guī)模較小的同性質(zhì)的問題，遞歸地調(diào)用同樣的方法求解這些問題，使這些問題最終簡(jiǎn)化成基礎(chǔ)問題。 算法21的遞歸基礎(chǔ)是n=0時(shí)，直接返回1（0！=1）。一般情況下，將fact(n)簡(jiǎn)化成規(guī)模較小的問題fact(n-1)，求出fact(n-1)后再與n相乘即求得了fact(n) 。 算法22的遞歸基礎(chǔ)是n=01. if(n0) /若n=0,則不需做任何動(dòng)作,僅當(dāng)n0時(shí)2. hanoi(n-1,x,z,y); /先將n-1個(gè)盤從x柱經(jīng)z柱搬到y(tǒng)柱 coutMove Disk n from x to zendl;/將第n個(gè)盤從x搬到z4. hanoi(n-1,y,x,z); /再將y柱上的n-1個(gè)盤經(jīng)x柱搬到z柱5. /if6./hanoi算法23 求解漢諾塔問題的遞歸算法3 背包問題 設(shè)有一個(gè)背包可以放入總重量為S的物品，現(xiàn)有n件物品，重量分別為w1 ，w2，wn 。問能否從這n件物品中選擇若干件放入背包，使得放入的物品總重量恰好為S。如果存在一組符合上述要求的物品，則稱此背包問題有解(用TRUE表示問題有解)，否則稱此問題無解(用FALSE表示無解)。假如我們定義一個(gè)維數(shù)組W存儲(chǔ)各物品的重量，用布爾函數(shù)knap(S,n)求解背包問題。其參數(shù)S表示背包還留有的容量，n為可供選擇的物品個(gè)數(shù)。顯然，如果S=0，背包問題總有解，即knap(0,n)為TRUE，因?yàn)椴贿x擇任何物品放入背包即可。當(dāng)S0但n0且n1，我們要求解背包問題有兩種途徑：一種是選擇第n件物品放入背包，于是背包剩余的容量為SWn(Wn中存儲(chǔ)wn ，即第n件物品的重量)，可選擇的物品是前n-1件。如果knapn(s-wn,n-1)有解，則knap(S,n)也有解，否則knap(S,n)無解，說明選擇第n件物品是錯(cuò)的。另一種是不選第n件物品，此時(shí)背包問題簡(jiǎn)化為knap(S,n-1)，如果它有解，則knap(S,n)也有解,如果它無解，則knap(S,n)也無解，從而背包問題可以遞歸地定義如下： TRUE 若S=0 knap(,n) = FALSE 若0且n0且n1上述遞歸定義是確定的，因?yàn)槊看芜f歸，n總減少1，S也可能減小Wn，所以遞歸若干次之后，遞歸基礎(chǔ)的條件（S0或n1）必定成立,所以遞歸過程在有限步之后總能結(jié)束。 例5 用遞歸方法求解背包問題。根據(jù)knap(S,n)的定義，容易寫出背包問題的遞歸算法，如算法24所示。const int MAXN=11; /假設(shè)最多只有十件物品int wMAXN=0,3,5,6,3,7,1,2,4,9,8; /假設(shè)物品的重量已存在w1.w10中int knap(int s,int n) / s為背包的容量,n為可供選擇物品的最大編號(hào)if(s=0) return TRUE; /若背包已裝滿,則有解if(s0)&(n1)return FALSE;/若背包容量為負(fù)數(shù)或已無物品可選,則必?zé)o解 if(knap(s-wn,n-1) /先試探將第n個(gè)物品裝入背包中,若因此有解,則原題有解 coutwn0)|!StackEmpty(s)/若尚未找到解且有物品可選或棧非空 if (n0) /如果還有物品可選 if (t=wn) /而且背包還能放得下 t-=wn; /就將物品n放入背包,t因此減少wn if (!StackFull(s) /若棧未滿 Push(s,n); /將n入棧,即將物品n放入背包 -n; /因此可選物品的編號(hào)小1 if (t=0) found=1; /若背包已滿,則求得一解 else exit(ERROR); /若棧已滿,則出錯(cuò) else -n; /若背包放不下物品n,則嘗試選擇物品n-1 /if(n0)/whileif (found) /如果找到一解,就將所選物品的重量輸出 for (i=s.top; i0; -i) Pop(s,e); coutwe0;-i) /first中存儲(chǔ)的數(shù)逐漸向第n個(gè)斐波那契數(shù)靠近 temp=first; first=second; second+=temp;/first移向下一個(gè)斐波那契數(shù)return first; /for語句結(jié)束時(shí),first已是第n個(gè)斐波那契數(shù)/Fibo算法28 求斐波那契數(shù)的非遞歸算法 顯然，也可以用圖10來解釋Fibo的執(zhí)行過程。由于Fibo消除了遞歸，省掉了n次函數(shù)調(diào)用的開銷，所以它的效率更高。 尾遞歸函數(shù)是一種特殊的遞歸函數(shù)。如果一個(gè)遞歸函數(shù)的返回值是直接計(jì)算而得或恰是一個(gè)遞歸調(diào)用自身而得到的返回值，那么這個(gè)遞歸函數(shù)就稱為尾遞歸函數(shù)。換句話說，如果遞歸函數(shù)中有一個(gè)遞歸調(diào)用（自身）的語句是這個(gè)函數(shù)的最后一個(gè)可執(zhí)行語句，那么這個(gè)函數(shù)就被稱做尾遞歸函數(shù)。應(yīng)該注意，最后一個(gè)可執(zhí)行語句并不一定是程序中的最后一條語句