數(shù)據(jù)結(jié)構(gòu)與算法—遞歸與非遞歸轉(zhuǎn)換

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

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

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

4、ecursive(Bitree T>/* if (T> inorder_recursive(T->lchild>。/*訪(fǎng)問(wèn)左子樹(shù) */visit(T> 。/* 訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn)*/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>。 /*訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn)*/push(S,p->rchild>。/*向右走,步*/3后序遍歷a遞歸方式void postorder_recursive(Bitree T>/*中序遍歷二叉樹(shù)的遞歸算法*/if (T> */visit(T>/*訪(fǎng)問(wèn)當(dāng)前結(jié)點(diǎn)*/b>非遞歸方式typedef struct BTNode* ptrenum 0,1,2 mark PMType 。/*有mark域的結(jié)點(diǎn)指針類(lèi)型*/void postorder_

6、non recursive(BiTree T>/*后續(xù)遍歷二叉樹(shù)的非遞歸算法PMType ain itstack(S>/* S的元素為PMType類(lèi)型*/push (S,T,0>/*根結(jié)點(diǎn)入棧*/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>/*訪(fǎng)問(wèn)左子樹(shù)*/breakcase 1:push(S,a,pt,2。/* 修改 mark 域

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

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

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

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

11、 + fn /4(n >= 2>這個(gè)例子相對(duì)簡(jiǎn)單一些，遞歸程序如下：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 。下面按照我們上面說(shuō)的，確定好遞歸調(diào)用樹(shù)的結(jié)構(gòu)，這一步是最重要的。首先，什么是葉子結(jié)點(diǎn)，我們看到當(dāng)n < 2 時(shí)f= n + 1，這就是返回的語(yǔ)句，有人問(wèn)為什么不是f = u1

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

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

14、底出錯(cuò)在哪里。ok，下面給出我花了兩天功夫想出來(lái)的非遞歸程序(再次提醒你不要?dú)怵H，大家都是這么過(guò)來(lái)的>。代碼:int stack20,flag20, cp。/*初始化棧和棧頂指針*/cp = 0。stack0 = n。flag0 =0。while(cp >= 0>switch(flagcp> case 0:/*訪(fǎng)問(wèn)的是根結(jié)點(diǎn)*/if (stackcp>=2> /*左子樹(shù)入棧 */flagcp=:1 。 /*修改標(biāo)志域*/cp+。stackcp=(i nt>(stackcp - 1 /2>。flagcp=:0 。 else /*否則為葉子結(jié)點(diǎn)*/s

15、tackcp += 1flagcp = 2。break。case 1:/*訪(fǎng)問(wèn)的是左子樹(shù)*/if (stackcp >= 2>/*右子樹(shù)入棧 */flagcp = 2。/* 修改標(biāo)志域*/cp +=2。4> 。stackcp =(in t>(stackcp - 2 /flagcp = 1。 else /*否則為葉子結(jié)點(diǎn)*stackcp += 1。flagcp = 2。break。case 2:/* */子樹(shù)嗎？ */if (flagcp -1 =2> /*當(dāng)前是右/* *如果是右子樹(shù)，那么對(duì)某一棵子樹(shù)的后序遍歷已經(jīng)*結(jié)束，接下來(lái)就是對(duì)這棵子樹(shù)的根結(jié)點(diǎn)的訪(fǎng)問(wèn)*/1。

16、stackcp-2 = stackcp * stackcp -flagcp - 2=2。cp = cp - 2。 else/*否則退回到后序遍歷的上一個(gè)結(jié)點(diǎn)*/cp-。breakreturn stackO算法分析：a>flag只有三個(gè)可能值：0表示第一次訪(fǎng)問(wèn)該結(jié)點(diǎn)，1表示訪(fǎng)問(wèn)的是 左子樹(shù)，2表示已經(jīng)結(jié)束了對(duì)某一棵子樹(shù)的訪(fǎng)問(wèn)，可能當(dāng)前結(jié)點(diǎn)是這棵子樹(shù)的右子樹(shù)，也可能是葉子結(jié)點(diǎn)。b>每遍歷到某個(gè)結(jié)點(diǎn)的時(shí)候，如果這個(gè)結(jié)點(diǎn)滿(mǎn)足葉子結(jié)點(diǎn)的條件，那么 把它的flag域設(shè)為2。否則根據(jù)訪(fǎng)問(wèn)的是根結(jié)點(diǎn)，左子樹(shù)或是右子樹(shù)來(lái)設(shè)置flag域，以便決定下一次訪(fǎng)問(wèn)該節(jié)點(diǎn)時(shí)的程序轉(zhuǎn)向。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需要說(shuō)明一

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

20、igh> 。 d> 葉子結(jié)點(diǎn)：當(dāng) low < high 時(shí)。e> 可以看出這是一個(gè)先序調(diào)用的二叉樹(shù)。棧：要保存的數(shù)據(jù)是兩個(gè)表示范圍的坐標(biāo)。代碼: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、 /* 對(duì)當(dāng)前結(jié)點(diǎn)的訪(fǎng)問(wèn) */cp+ 。mcp = mcp - 1。n cp = p - 1。/*向右走一步*/mcp + 1 = n cp + 2。ncp + 1 = ncp - 1。cp+ 。四、遞歸程序的分類(lèi)及用途遞歸程序分為兩類(lèi)：尾部遞歸和非尾部遞歸。上面提到的幾個(gè)例子都是非尾部遞 歸，在一個(gè)選擇分支中有至少一個(gè)的遞歸調(diào)用。相對(duì)而言，尾部遞歸就容易很多了，因?yàn)?與非尾部遞歸相比，每個(gè)選擇分支只有一個(gè)遞歸調(diào)用，我們?cè)诮鉀Q的時(shí)候就不需要使用到棧，只要循環(huán)和設(shè)置好循環(huán)體就可以了。下面再舉 幾個(gè)尾部遞歸的例子吧，比較簡(jiǎn)單我就不多說(shuō)什么了。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+。分析完了遞歸程序的分類(lèi)，讓我們回頭看看在向非遞歸轉(zhuǎn)換的過(guò)程中

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