數(shù)據(jù)結構與算法—遞歸與非遞歸轉換

1、遞歸與非遞歸轉換的基礎知識是能夠正確理解三種樹的遍歷方法：前序，中序和后序，第一篇就是關于這三種遍歷方法的遞歸和非遞歸算法。一、 為什么要學習遞歸與非遞歸的轉換的實現(xiàn)方法？1>并不是每一門語言都支持遞歸的。2>有助于理解遞歸的本質。3>有助于理解棧，樹等數(shù)據(jù)結構。二、三種遍歷樹的遞歸和非遞歸算法遞歸與非遞歸的轉換基于以下的原理：所有的遞歸程序都可以用樹結構表示出來。需要說明的是，這個”原理”并沒有經(jīng)過嚴格的數(shù)學證明，只是我的一個猜想，不過在至少在我遇到的例子中是適用的。學習過樹結構的人都知道，有三種方法可以遍歷樹：前序，中 序，后序。理解這三種遍歷方式的遞歸和非遞歸的表達方式

2、是能夠正確實現(xiàn)轉換的關鍵之處，所以我們先來談談這個。需要說明的是，這里以特殊的二叉樹來說明，不過大多數(shù)情 況下二叉樹已經(jīng)夠用，而且理解了二叉樹的遍歷，其它的樹遍歷方式就不難了。1>前序遍歷a>遞歸方式：void preorder_recursive(Bitree T> /*先序遍歷二叉樹的遞歸算法*/if (T> visit(T>。/* 訪問當前結點*/preorder_recursive(T->lchild>。/* 訪問左子樹 */preorder_recursive(T->rchild>。/* 訪問右子樹 */b>非遞歸方式法*/

3、in itstack(S> 。push(S,T> 。/*根指針進棧*/while(!stackempty(S>> while(gettop(S,p>&&p> /*向左走到盡頭 */visit(p>。/*每向前走一步都訪問當前結點*/push(S,p->lchild>。pop(S,p> 。if(!stackempty(S>> /*向右走一步 */pop(S,p>。push(S,p->rchild>。2>中序遍歷a>遞歸方式中序遍歷二叉樹的遞歸算法*/void ino rder_r

4、ecursive(Bitree T>/* if (T> inorder_recursive(T->lchild>。/*訪問左子樹 */visit(T> 。/* 訪問當前結點*/b非遞歸方式void ino rder_ non recursive(Bitree T>in itstack(S>/*初始化棧*/push(S,T> 。/*根指針入棧*/while (!stackempty(S>> while (gettop(S, p> && p>/*向左走到盡頭*/push(S,p->lchild>po

5、p(S,p>/*空指針退棧*/if (!stackempty(S>> pop(S,p>visit(p>。 /*訪問當前結點*/push(S,p->rchild>。/*向右走,步*/3后序遍歷a遞歸方式void postorder_recursive(Bitree T>/*中序遍歷二叉樹的遞歸算法*/if (T> */visit(T>/*訪問當前結點*/b>非遞歸方式typedef struct BTNode* ptrenum 0,1,2 mark PMType 。/*有mark域的結點指針類型*/void postorder_

6、non recursive(BiTree T>/*后續(xù)遍歷二叉樹的非遞歸算法PMType ain itstack(S>/* S的元素為PMType類型*/push (S,T,0>/*根結點入棧*/while(!stackempty(S>> pop(S,a>switch(a,mark>case 0:push(S,a.ptr，1>。/* 修改mark域*/if(a.ptr->lchild>push(S,a,ptr->lchild,0>/*訪問左子樹*/breakcase 1:push(S,a,pt,2。/* 修改 mark 域

7、 */if(a.ptr-rchildpush(S,a.ptr-rchild,O。 /* 訪問右子樹 */break。case 2:visit(a.ptr。/*訪問結點 */三、實現(xiàn)遞歸與非遞歸的換轉原理和例子一)原理分析通常，一個函數(shù)在調用另一個函數(shù)之前，要作如下的事情：a將實在參數(shù)，返回地址等信息傳遞給被調用函數(shù)保存。b為被調用函數(shù)的局部變量分配存儲區(qū)。c將控制轉移到被調函數(shù)的入口。從被調用函數(shù)返回調用函數(shù)之前，也要做三件事情：a保存被調函數(shù)的計算結果。b釋放被調函數(shù)的數(shù)據(jù)區(qū)。c依照被調函數(shù)保存的返回地址將控制轉移到調用函數(shù)。所有的這些，不論是變量還是地址，本質上來說都是”數(shù)據(jù)”都是保存在系

8、統(tǒng)所分配的棧中的。ok，到這里已經(jīng)解決了第一個問題：遞歸調用時數(shù)據(jù)都是保存在棧中的，有多少個數(shù)據(jù)需要保存就要設置多少個棧，而且最重要的一點是：控制所有這些棧的棧頂指針都 是相同的，否則無法實現(xiàn)同步。下面來解決第二個問題：在非遞歸中，程序如何知道到底要轉移到哪個部分繼續(xù)執(zhí)行？回到上面說的樹的三種遍歷方式，抽象出來只有三種操作：訪問當前結點，訪問左子樹，訪問右子樹。這三種操作的順序不同，遍歷方式也不同。如果我們再抽象一點，對 這三種操作再進行一個概括，可以得到：a訪問當前結點：對目前的數(shù)據(jù)進行一些處理。b訪問左子樹：變換當前的數(shù)據(jù)以進行下一次處理。c訪問右子樹：再次變換當前的數(shù)據(jù)以進行下一次處理(

9、與訪問左子樹所不同的方式。F面以先序遍歷來說明:if (T> visit(T>/* 訪問當前結點*/* 訪問左子樹*/* 訪問右子樹*/preorder_recursive(T->lchild> preorder_recursive(T->rchild>visit(T>這個操作就是對當前數(shù)據(jù)進行的處理，preorder_recursive(T->lchild>就是把當前 數(shù)據(jù)變換為它的左子樹，訪問右子樹的操作可以同樣理解了?，F(xiàn)在回到我們提出的第二個問題：如何確定轉移到哪里繼續(xù)執(zhí)行？關鍵在于一下三個地方：a>確定對當前數(shù)據(jù)的訪問順序，簡

10、單一點說就是確定這個遞歸程序可以轉換為哪種方式遍歷的樹結構。b>確定這個遞歸函數(shù)轉換為遞歸調用樹時的分支是如何劃分的， 即確定什么是這個遞歸調用樹的”左子樹”和”右子樹” c>確定 這個遞歸調用樹何時返回，即確定什么結點是這個遞歸調用樹的”葉子結點”。二)兩個例子好了上面的理論知識已經(jīng)足夠了，下面讓我們看看幾個例子，結合例子加深我們 對問題的認識。即使上面的理論你沒有完全明白，不要氣餒，對事物的認識總是曲折的， 多看多想你一定可以明白(事實上我也是花了兩個星期的時間才弄得比較明白得>。1> 例 1 :f(n> = n +1。 (n <2 >=fn /2

11、 + fn /4(n >= 2>這個例子相對簡單一些，遞歸程序如下：int f_recursive(i nt n>int u1, u2, f。if (n < 2>f = n + 1。else u1 = f_recursive(i nt>(n/2>> u2 = f_recursive(i nt>(n/4>> f = u1 * u2 。return f 。下面按照我們上面說的，確定好遞歸調用樹的結構，這一步是最重要的。首先，什么是葉子結點，我們看到當n < 2 時f= n + 1，這就是返回的語句，有人問為什么不是f = u1

12、 * u2，這也是一個返回的語句呀 ？答案是：這條語句是在 u1 = exmp1(int>(n/2>> 和u2 = exmp1(int>(n/4>>之后 執(zhí)行的，是這兩條語句的父結點。其次，什么是當前結點，由上面的分析，f = u1 * u2即是父結點。然后，順理成章的 u1 = exmp1(int>(n/2>>和 u2 = exmp1(int>(n/4>>就分別是左子樹和右子樹了。最后，我們可以看到，這個遞歸函數(shù)可以表示成后序遍歷的 二叉調用樹。好了，樹的情況分析到這里，下面來分析一下棧的情況，看看我們要把什么數(shù)據(jù)保存在

13、棧中：非遞歸程序中我們已經(jīng)看到了要加入一個標志域，因此在棧中要保存這個標志域。另外，u1，u2和每次調用遞歸函數(shù)時的n/2和n/4參數(shù)都要保存，這樣就要分別有三個棧分別保存：標志域，返回量和參數(shù)，不過我們可以做一個優(yōu)化，因為在向上一層 返回的時候，參數(shù)已經(jīng)沒有用了，而返回量也只有在向上返回時才用至打因此可以把這兩個棧合為一個棧。如果對于上面的分析你沒有明白，建議你根據(jù)這個遞歸函數(shù)寫出它的遞 歸棧的變化情況以加深理解，再次重申一點：前期對樹結構和棧的分析是最重要的，如果你的程序出錯，那么請返回到這一步來再次分析，最好把遞歸調用樹和棧的變化情況都畫 出來，并且結合一些簡單的參數(shù)來人工分析你的算法到

14、底出錯在哪里。ok，下面給出我花了兩天功夫想出來的非遞歸程序(再次提醒你不要氣餒，大家都是這么過來的>。代碼:int stack20,flag20, cp。/*初始化棧和棧頂指針*/cp = 0。stack0 = n。flag0 =0。while(cp >= 0>switch(flagcp> case 0:/*訪問的是根結點*/if (stackcp>=2> /*左子樹入棧 */flagcp=:1 。 /*修改標志域*/cp+。stackcp=(i nt>(stackcp - 1 /2>。flagcp=:0 。 else /*否則為葉子結點*/s

15、tackcp += 1flagcp = 2。break。case 1:/*訪問的是左子樹*/if (stackcp >= 2>/*右子樹入棧 */flagcp = 2。/* 修改標志域*/cp +=2。4> 。stackcp =(in t>(stackcp - 2 /flagcp = 1。 else /*否則為葉子結點*stackcp += 1。flagcp = 2。break。case 2:/* */子樹嗎？ */if (flagcp -1 =2> /*當前是右/* *如果是右子樹，那么對某一棵子樹的后序遍歷已經(jīng)*結束，接下來就是對這棵子樹的根結點的訪問*/1。

16、stackcp-2 = stackcp * stackcp -flagcp - 2=2。cp = cp - 2。 else/*否則退回到后序遍歷的上一個結點*/cp-。breakreturn stackO算法分析：a>flag只有三個可能值：0表示第一次訪問該結點，1表示訪問的是 左子樹，2表示已經(jīng)結束了對某一棵子樹的訪問，可能當前結點是這棵子樹的右子樹，也可能是葉子結點。b>每遍歷到某個結點的時候，如果這個結點滿足葉子結點的條件，那么 把它的flag域設為2。否則根據(jù)訪問的是根結點，左子樹或是右子樹來設置flag域，以便決定下一次訪問該節(jié)點時的程序轉向。2> 例 2:int

17、 low ， int high>快速排序算法遞歸算法如下:void swap(i nt arrayint temp 。temp = arraylow arraylow = arrayhigh arrayhigh = tempint partiti on (i nt array， int low ， int high>int p 。p = arraylow 。while (low < high> while (low < high && arrayhigh >= p>high_-swap(array , low , high> 。

18、while (low < high && arraylow <= p> low+ 。swap(array , low , high> 。return low 。int low , int high>low , high> 。,low , p - 1>。,p + 1, high> 。void qsort_recursive(i nt arrayint p 。if(low < high> p = partiti on( arrayqsort_recursive(arrayqsort_recursive(array需要說明一

19、下快速排序的算法：partiti on函數(shù)根據(jù)數(shù)組中的某一個數(shù)把數(shù)組劃分為兩個部分，左邊的部分均不大于這個數(shù)，右邊的數(shù)均不小于這個數(shù)，然后再對左右兩邊 的數(shù)組再進行劃分。這里我們專注于遞歸與非遞歸的轉換，partition函數(shù)在非遞歸函數(shù)中同樣的可以調用(其實partition函數(shù)就是對當前結點的訪問>。再次進行遞歸調用樹和棧的分析：遞歸調用樹：a>對當前結點的訪問是調用partition 函數(shù)。b> 左子樹： qsort_recursive(array ， low ， p - 1>。 c> 右子樹： qsort_recursive(array ， p +1， h

20、igh> 。 d> 葉子結點：當 low < high 時。e> 可以看出這是一個先序調用的二叉樹。棧：要保存的數(shù)據(jù)是兩個表示范圍的坐標。代碼:void qsort_ non recursive(i nt arrayint low , int highint m50, n50 , cp , p。cp = 0。m0 = low 。n0 = high 。 /* 初始化棧和棧頂指針 */while (mcp < n cp> while (mcp < n cp> /*向左走到盡頭 */p = partition(array, mcp , ncp>。

21、 /* 對當前結點的訪問 */cp+ 。mcp = mcp - 1。n cp = p - 1。/*向右走一步*/mcp + 1 = n cp + 2。ncp + 1 = ncp - 1。cp+ 。四、遞歸程序的分類及用途遞歸程序分為兩類：尾部遞歸和非尾部遞歸。上面提到的幾個例子都是非尾部遞 歸，在一個選擇分支中有至少一個的遞歸調用。相對而言，尾部遞歸就容易很多了，因為 與非尾部遞歸相比，每個選擇分支只有一個遞歸調用，我們在解決的時候就不需要使用到棧，只要循環(huán)和設置好循環(huán)體就可以了。下面再舉 幾個尾部遞歸的例子吧，比較簡單我就不多說什么了。1> 例 1:g(m , n> = 0 (m

22、 = 0, n >= 0>=g(m - 1, 2n> + n 。(m > 0,a>遞歸程序int g_recursive(i nt m , int n>if (m = 0 && n >= 0>return 0。return (g_recurse(m - 1, 2*n> + n>b>非遞歸程序int g_non recursive(i nt m, int n>int p 。for (p = 0。 m > 0 && n >= 0。 m-,p += n 。return p 。2>

23、 例 2:f(n> = n + 1 (n = 0>n >= 0>n *= 2>=n * f(n/2> (n > 0>a>遞歸程序int f_recursive(i nt n>if (n = 0>return 1。return (n * f_recurse( n/2>>。b>非遞歸程序int f_non recursive(i nt n>int m 。for (m = 1。n > 0 。n /= 2>m *= n 。return m+。分析完了遞歸程序的分類，讓我們回頭看看在向非遞歸轉換的過程中

24、用到了什么來實現(xiàn)轉換：1>循環(huán)，因為程序要在某個條件下一直執(zhí)行下去，要代替遞歸程序，循環(huán)必不可 少，對于尾部遞歸，循環(huán)結束的條件十分容易確定，只要按照不同分支的條件寫出來就可以了。而對于非尾部遞歸程序，循環(huán)結束的條件一般是當棧為空時或者是結束了對遞歸調 用樹的遍歷從樹的根結點退出時，而且有的時候寫成while(>的形式，有時寫成 do。while的形式(如上面的akm函數(shù) >，具體怎樣，很難說清楚，取決于你對整個遞 歸程序的分析。2遞歸調用樹，樹的結構在轉換的過程中是不可見的，你不必為轉換專門寫一個 樹結構，不過能不能把遞歸調用中的樹遍歷方式以及葉子結點，左子樹，右子樹等元素確定好是你能否正確解決問題的關鍵（這一點已經(jīng)在上面的分析過程中展露無疑，確定好這些后，剩下的工作大部分就是按照給出的幾種不同的遍歷樹的方式把程序進行改寫，