_遞歸馮文科一、遞歸的基本概念。一個函數、概念或數學結構，如果在其定義或說明內部直接或間接地出現對其本身的引用，或者是為了描述問題的某一狀態，必須要用至它的上一狀態，而描述上一狀態，又必須用到它的上一狀態這種用自己來定義自己的方法，稱之為遞歸或遞歸定義。在程序設計中，函數直接或間接調用自己，就被稱為遞歸調用。二、遞歸的最簡單應用：通過各項關系及初值求數列的某一項。在數學中，有這樣一種數列，很難求出它的通項公式，但數列中各項間關系卻很簡單，于是人們想出另一種辦法來描述這種數列：通過初值及與前面臨近幾項之間的關系。要使用這樣的描述方式，至少要提供兩個信息：一是最前面幾項的數值，一是數列間各項的關系。比如階乘數列1、2、6、24、120、720如果用上面的方式來描述它，應該是：如果需要寫一個函數來求的值，那么可以很容易地寫成這樣：int f(int n)if(n=1)return 1; return n*f(n-1);這就是遞歸函數的最簡單形式，從中可以明顯看出遞歸函數都有的一個特點：先處理一些特殊情況這也是遞歸函數的第一個出口，再處理遞歸關系這形成遞歸函數的第二個出口。遞歸函數的執行過程總是先通過遞歸關系不斷地縮小問題的規模，直到簡單到可以作為特殊情況處理而得出直接的結果，再通過遞歸關系逐層返回到原來的數據規模，最終得出問題的解。以上面求階乘數列的函數為例。如在求時，由于3不是特殊值，因此需要計算，但是對它自己的調用，于是再計算，2也不是特殊值，需要計算，需要知道的值，再計算，1是特殊值，于是直接得出，返回上一步，得，再返回上一步，得，從而得最終解。用圖解來說明，就是的執行過程（特殊值判斷：），繼續向下。（遞歸關系處理：）求，需要先計算，調用，且本身掛起得到，由正常出口返回的執行過程（特殊值判斷：），繼續向下。（遞歸關系處理：）求，需要先計算，調用，且本身掛起得到，由正常出口返回的執行過程（特殊值判斷：），由特殊情況出口直接返回1。下面再看一個稍復雜點的例子。【例1】數列的前幾項為1、輸入，編程求的精確分數解。分析：這個題目較易，發現，其它情況下有。如要求實數解的話，這基本已經可以寫出遞歸函數了。但由于題目要求精確的分數解，還需做一些調整。設，則由遞歸關系，有，再約分化簡，即得。但發現一個問題：求出時，需要返回兩個整數：分子與分母，而通常的函數只能返回一個整數。這個問題一般有兩類解決辦法，一種是讓求值函數返回一個結構體變量，這樣就可以返回兩個變量了（其實還可以不只兩個呢）；另一種是在求值函數的參數表中加入兩個指針變量或引用變量，通過參數給帶回數值。但由于后一種做法會使程序結構不清晰返回值是由參數表得到的，因此我們使用前一種方法。另外，在通過得出后，就已經是最簡分數了，無須化簡。證明如下：若是最簡分數，即說明的最大公約數為1，即對任何，都有與不全為0，不防記、，則有只要與不全為0，且，就有與不全為0。因此對任何的，有與不全為0。而對于的情況而言，記，則有由于，因此同樣有與不全為0。所以對任意，都有與不全為0，因此它們的最大公約數為1，即是最簡分數。雖然這是個要求（即）是最簡分數的結論，但由于數列第二項為，是最簡分數，因此可以證明第三項也是最簡分數，同時也證明對所有的，求出的就是最簡分數，無須化簡。具體代碼如下：/ 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;三、遞歸的精髓：只考慮當前一步，剩下的讓下一步去做吧。對大多數問題而言，當它的規模縮小至“特殊情況”時，都可以非常輕易地得出問題的解，因此我們不過多地討論“特殊情況”，只詳細地討論遞歸關系的確定。尋找遞歸關系，最低標準是它能使問題的規模變小，且變小后的問題與原問題在本質上是一樣的。當找到遞歸關系后，我們的遞歸函數只須處理特殊情況與遞歸關系，不需要處理其它的信息至于下一步的事情，就讓下一步去做吧。另一個需要考慮的事情就是遞歸函數的參數表，首先，在通常情況下，參數表都要使用變量參數，且遞歸函數中盡量使用局部變量這會減少很多不必要的麻煩；其次，參數表中，大多都有一個表示當前在執行第幾步的參數。【例2】下圖是一個有向圖，輸入，打印的所有路徑。1357902468分析：仔細研究這個圖的特點，發現以下規律：對任何結點，都可以走到和，當然如果它們不超過9的話。由于要打印路徑，因此需要保存查找過程中的部分路徑信息。可以做一個全局數組path來存儲這個信息，由于結點0沒有來路，且是所有路徑的起點，因此記path0=0，遞歸函數負責填寫之后的路徑結點。我們這樣設計遞歸函數：首先，這個遞歸函數的參數表中至少需要一個參數i，它的意義是表示現在在填路徑中的第幾個結點，而pathi可以填的數，要么是上一個結點加1，要么是上一個結點加2，即pathi=pathi-1+1或pathi=pathi-1+2；其次，特殊情況的討論：我們要找的是終止到的路徑，因此若出現pathi-1=的情況，就說明已經找到路徑，無須將當前層再填入結點，可以將path中的信息輸出并結束函數了這是遞歸函數的特殊情況出口；第三、遞歸關系的處理：若還沒到達結點，則填寫本結點pathi，上文已說明，pathi=pathi-1+1或pathi=pathi-1+2，當然如果它們都不過9的話。將結點填好后，說明路徑向下走了一步，距離結點更近了一步，問題規模已經變小。不要處理其它東西，直接遞歸，通過遞歸調用去填寫i+1結點就可以了。這里有處和【例1】不相同的地方，即pathi是有兩種可能可選的，我們的處理這這樣的，先令pathi=pathi-1+1，然后遞歸調用，填寫i+1結點，當這個調用返回時，說明所有pathi為pathi-1+1的路徑都已經討論完成了，再令pathi=pathi-1+2，再遞歸，當它返回時，整個函數執行完畢，形成正常的執行完成時的出口。具體代碼如下：/ 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時代開始就已經有了，雖然功能與Photoshop不能相比，但它小巧而迅速，一般的簡單功能還是很方便的。畫筆中的填色工具是油漆桶，選定它，再指定一個顏色，在圖片中一點，所有與這個點顏色相同且相連的象素就都被填充了。如下圖示：畫筆的油漆桶工具填充的是一個叫“四連通”的區域，即它只從上、下、左、右四個方向向外擴展。請編寫程序，模擬油漆通工具。輸入文件：Exam3In.txt中有10行，每行是一個10字符的字符串，表示一個10*10的圖象，不同的字符表示不同的顏色；之后的一行有兩個用空格分開的整數，表示油漆桶點中的位置，再后面一行是一個字符，表示油漆桶的填充顏色。輸出文件：Exam3Out.txt，輸出10行，每行10個字符的字符串，表示填充后的圖象。分析：本題給了一個點的位置，查找所有與它“四連通”的點就成為本題的核心問題。我們的算法是這樣的：先從這個起點出發，沿四個方向展開，看這“直接相連”的四個點是否可以填充，若有可以的，則再以這個點為中心，再向四個方向展開直到所有可能展開的點都不能再展開了為止。遞歸函數這樣設計：首先它的參數表需要兩個參數，表示本次從哪個位置點展開；其次，依次討論它四個方向上相鄰的點是否可填充與起點顏色相同，如果可以，則填充，并以此點為中心，遞歸調用。代碼如下：/ 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;本題中的遞歸函數fill似乎與常規的遞歸函數比較起來缺少了處理特殊情況的部分，其實不然，它的特殊情況處理已經被融合到遞歸關系的處理當中了，正常與非正常的出口合并到一起。特殊情況就是：當向四個方向都無法展開時，程序直接退出。這個程序的fill函數運用的算法就是“種子填充算法”的遞歸寫法。它另有動態規劃的寫法當然比這個要快得多，大家可以想一想如何實現。四、遞歸函數的必然用法：處理遞歸定義的數據結構。一些常用的數據結構本身就是遞歸定義的，寫一個遞歸的函數來處理它，當然是再正常不過的事情，就比如說二叉樹、廣義表【例4】二叉樹的操作。用字符串的形式給定一個完全二叉樹，保存在輸入文件Exam4In.txt中，編寫程序輸出其后序遍歷的結果至輸出文件Exam4Out.txt中。分析：本題的程序是簡單的，唯一要注意的是：C+的數組從下標0開始，因此對于結點,它的左孩子編號應該是，右孩子編號應該是。其它的地方沒什么難度。代碼如下：/ 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】以字符串形式給出一棵完全二叉樹的先序遍歷與中序遍歷序列，編程輸出用字符串形式表示的完全二叉樹的結構。分析：先序遍歷的首結點一定是整棵樹的根，因此可以直接標在0處。在中序遍歷序列中，它左邊的結點構成左子樹，右邊的結點構成右子樹，從而可以知道，左子樹與右子樹的結點個數，進而得到及左子樹與右子樹的先序遍歷與中序遍歷序列，遞歸查找所有子樹的根即可。為了得到整棵樹的結構，設置全局數組tree來存儲，全局數組s的意義是：si存儲整數表示第i層結點的起始下標。代碼如下：/ 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;五、遞歸與回溯法。遞歸的另一個常用的地方是實現回溯法。所謂回溯法，一般就是指先將問題分成幾步，在每一步時嘗試所有的可能，直到達到最終要求，或最后一步將所有可能嘗試完成后，再回到上一步，使上一步嘗試下一種可能，并繼續的作法。由于回溯的“步驟性”明顯，因此用遞歸實現回溯是相當方便的事。看下面的一個例題：【例6】n皇后問題。輸入整數n，打印n皇后問題的所有解及解的總數。代碼如下：/ 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;六、練習【練習】為給定的表達式建立表達式樹，并求值。給定的表達式中，所有數字都是1位正整數，出現的符號可能為、*、/、（、）。分析：這是一個與一般數據結構書上講的用棧計算的方法本質不同的方法。在詳細說明這個算法之前，需要首先明確這個算法用到的概念1、單元：一個單元可能是用括號括起來的一個表達式，或是一個整數；2、項：一個項是指由*與/連接起來的若干單元；3、表達式：一個表達式是指由或連接起來的若干項。要建立表達式樹，需要三個函數互相調用的函數：一個是getunit，用于建立一個單元；一個是getexpr，用于建立一個項，另一個就是build，用于建立一個表達式。getunit函數較易，如果字符串首字母是（的話，那么從它后面的字符開始用build建立一個表達式，這個表達式就是一個單元；否則，就處理一個整數；getexpr函數是建立在getunit之上的，它先用getunit建立一個單元，然后不停地考察之后地連接符號是不是*或/，若是，則不停地重復讀連接符、建立另一個單元、建立連接的操作，直到連接符號不是*或/為止。build函數是用于最終建立表達式的，它先用getexpr建立一個項，再用符號將剩余的各項連接成二叉樹。代碼如下：/ 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又例如，Fibonacci(斐波那契)數列可遞歸定義為 0 若n=0Fib(n) = 1 若n=1 Fib(n-1)+Fib(n-2) 若n1 據此可以寫出實現求n 的階乘和求Fibonacci數列中第n項的遞歸算法，如算法21和算法22所示。long int fact(int n) /求非負整數n的階乘if(!n) return 1; /0!=1else return n*fact(n-1); /n!=n*(n-1)!/fact算法21 求階乘的遞歸算法long int fib(int n) /求斐波那契數列中的第n個數if(n1,f(n)=f(n-1)+f(n-2)/fib算法22 求斐波那契數的遞歸算法 一般地說，每一個遞歸函數的定義都包含兩個部分。(1) 遞歸基礎 對無需遞歸的規模最小的問題直接進行處理。(2) 遞歸步驟 將一般情況的問題簡化成一個或多個規模較小的同性質的問題，遞歸地調用同樣的方法求解這些問題，使這些問題最終簡化成基礎問題。 算法21的遞歸基礎是n=0時，直接返回1（0！=1）。一般情況下，將fact(n)簡化成規模較小的問題fact(n-1)，求出fact(n-1)后再與n相乘即求得了fact(n) 。 算法22的遞歸基礎是n=01. if(n0) /若n=0,則不需做任何動作,僅當n0時2. hanoi(n-1,x,z,y); /先將n-1個盤從x柱經z柱搬到y柱 coutMove Disk n from x to zendl;/將第n個盤從x搬到z4. hanoi(n-1,y,x,z); /再將y柱上的n-1個盤經x柱搬到z柱5. /if6./hanoi算法23 求解漢諾塔問題的遞歸算法3 背包問題 設有一個背包可以放入總重量為S的物品，現有n件物品，重量分別為w1 ，w2，wn 。問能否從這n件物品中選擇若干件放入背包，使得放入的物品總重量恰好為S。如果存在一組符合上述要求的物品，則稱此背包問題有解(用TRUE表示問題有解)，否則稱此問題無解(用FALSE表示無解)。假如我們定義一個維數組W存儲各物品的重量，用布爾函數knap(S,n)求解背包問題。其參數S表示背包還留有的容量，n為可供選擇的物品個數。顯然，如果S=0，背包問題總有解，即knap(0,n)為TRUE，因為不選擇任何物品放入背包即可。當S0但n0且n1，我們要求解背包問題有兩種途徑：一種是選擇第n件物品放入背包，于是背包剩余的容量為SWn(Wn中存儲wn ，即第n件物品的重量)，可選擇的物品是前n-1件。如果knapn(s-wn,n-1)有解，則knap(S,n)也有解，否則knap(S,n)無解，說明選擇第n件物品是錯的。另一種是不選第n件物品，此時背包問題簡化為knap(S,n-1)，如果它有解，則knap(S,n)也有解,如果它無解，則knap(S,n)也無解，從而背包問題可以遞歸地定義如下： TRUE 若S=0 knap(,n) = FALSE 若0且n0且n1上述遞歸定義是確定的，因為每次遞歸，n總減少1，S也可能減小Wn，所以遞歸若干次之后，遞歸基礎的條件（S0或n1）必定成立,所以遞歸過程在有限步之后總能結束。 例5 用遞歸方法求解背包問題。根據knap(S,n)的定義，容易寫出背包問題的遞歸算法，如算法24所示。const int MAXN=11; /假設最多只有十件物品int wMAXN=0,3,5,6,3,7,1,2,4,9,8; /假設物品的重量已存在w1.w10中int knap(int s,int n) / s為背包的容量,n為可供選擇物品的最大編號if(s=0) return TRUE; /若背包已裝滿,則有解if(s0)&(n1)return FALSE;/若背包容量為負數或已無物品可選,則必無解 if(knap(s-wn,n-1) /先試探將第n個物品裝入背包中,若因此有解,則原題有解 coutwn0)|!StackEmpty(s)/若尚未找到解且有物品可選或棧非空 if (n0) /如果還有物品可選 if (t=wn) /而且背包還能放得下 t-=wn; /就將物品n放入背包,t因此減少wn if (!StackFull(s) /若棧未滿 Push(s,n); /將n入棧,即將物品n放入背包 -n; /因此可選物品的編號小1 if (t=0) found=1; /若背包已滿,則求得一解 else exit(ERROR); /若棧已滿,則出錯 else -n; /若背包放不下物品n,則嘗試選擇物品n-1 /if(n0)/whileif (found) /如果找到一解,就將所選物品的重量輸出 for (i=s.top; i0; -i) Pop(s,e); coutwe0;-i) /first中存儲的數逐漸向第n個斐波那契數靠近 temp=first; first=second; second+=temp;/first移向下一個斐波那契數return first; /for語句結束時,first已是第n個斐波那契數/Fibo算法28 求斐波那契數的非遞歸算法 顯然，也可以用圖10來解釋Fibo的執行過程。由于Fibo消除了遞歸，省掉了n次函數調用的開銷，所以它的效率更高。 尾遞歸函數是一種特殊的遞歸函數。如果一個遞歸函數的返回值是直接計算而得或恰是一個遞歸調用自身而得到的返回值，那么這個遞歸函數就稱為尾遞歸函數。換句話說，如果遞歸函數中有一個遞歸調用（自身）的語句是這個函數的最后一個可執行語句，那么這個函數就被稱做尾遞歸函數。應該注意，最后一個可執行語句并不一定是程序中的最后一條語句