學號： 2006011269 哈爾濱師范大學 學士學位論文 題 目 算法設計中的遞歸與非遞歸轉換 學 生 孫慶雨 指導教師 欒叢海 講師 年 級 2006 級 專 業(yè) 信息與計算科學 系 別 信息科學系 學 院 數學科學學院 哈 爾 濱 師 范 大 學 學士學位論文開題報告 論文題目 算法設計中的遞歸與非遞歸轉換 學生姓名 孫慶雨 指導教師 欒叢海 講師 年 級 2006 級 專 業(yè) 信息與計算科學 2009 年 11 月 課題來源： 自選題目 課題研究的目的和意義： 1.并不是每一門語言都支持遞歸的 . 2.有助于理解遞歸的本質 . 3.有助于理解棧 、 樹等數據結構 . 國內外同類課題研究現狀及發(fā)展趨勢： 近年來 ,計算機科學技術與計算機應用以驚人的速度發(fā)展 。 它已滲透到了人類生活的每一角 落 .現代社會的各個領域無一例外地廣泛使用著電子計算機 .計算機知識已成為當代人類文化不可缺少的重要組成部分 .研究與使用算法設計已成為必然 . 在計算機編寫程序中 ,遞歸算法對解決一大類問題是十分有效的 ,它往往使算法的描述簡潔而且易于理解 . 課題研究的主要內容和方法，研究過程中的主要問題和解決辦法： 主要內容：算法設計中的遞歸和非遞歸轉換 主要方法：用棧來解決算法設計中的遞歸和非遞歸轉換 主要問題： 實現算法設計中的遞歸和非遞歸轉換 解決方法：利用循環(huán)，遞歸調用樹，棧實現算法設計中的遞歸和非遞歸轉換 課題研究起止時間和進度安排： 2009 年 12 月 2 日 2010 年 2 月 9 日 課題資料搜集整理 2010 年 2 月 9 日 2010 年 4 月 6 日 材料分析、撰 寫論文 2010 年 4 月 20 日 完成論文撰寫、成稿 課題研究所需主要設備、儀器及藥品： 計算機 外出調研主要單位，訪問學者姓名： 指導教師審查意見： 指導教師 （簽字） 年 月 教研室（研究室）評審意見： _教研室（研究室）主任 （簽字） 年 月 系（部）主任審查意見： _系（部）主任 （簽字） 年 月 學 士 學 位 論 文 題 目 算法設計中的遞歸與非遞歸轉換 學 生 孫慶雨 指導教師 欒叢海 講師 年 級 2006 級 專 業(yè) 信息與計算科學 系 別 信息科學系 學 院 數學科學學院 哈爾濱師范大學 2010 年 5 月 算法設計中的遞歸和非遞歸轉換 孫慶雨 摘要 ： 算法設計中的遞歸和非遞歸轉換是學習算法設計的基礎， 熟練地運用遞歸與非遞歸轉 換是算法設計的基礎，在這篇論文中我就介紹幾種算法設計中的遞歸與非遞歸的轉換方法 .讓大家可以更好的實現算法設計中的遞歸和非遞歸轉換。 關鍵詞 ： 算法設計 遞歸與非遞歸 轉換 三種遍歷樹的算法 遞歸與非遞歸轉換的基礎知識是能夠正確 理解三種樹的遍歷方法：前序，中序和后序，第一篇就是關于這三種遍歷方法的遞歸和非遞歸算法。 一、 為什么要學習遞歸與非遞歸的轉換的實現方法 1.并不是每一門語言都支持遞歸的 . 2.有助于理解遞歸的本質 . 3.有助于理解棧 ,樹等數據結構 . 二 、 三種遍歷樹的遞歸和非遞歸算法 遞歸與非遞歸的轉換基于以下的原理 :所有的遞歸程序都可以用樹結構表示出來 .需要說明的是 ,這個 原理 并沒有經過嚴格的數學證明 ,只是我的一個猜想 ,不過在至少在我遇到的例子中是適用的 .學習過樹結構的人都 知道 ,有三種方法可以遍歷樹 :前序 ,中序 ,后序 .理解這三種遍歷方式的遞歸和非遞歸的表達方式是能夠正確實現轉換的關鍵之處 ,所以我們先來談談這個 .需要說明的是 ,這里以特殊的二叉樹來說明 ,不過大多數情況下二叉樹已經夠用 ,而且理解了二叉樹的遍歷 ,其它的樹遍歷方式就不難了。 1)前序遍歷 a)遞歸方式 : void preorder_recursive(Bitree T) /* 先序遍歷二叉樹的遞歸算法 */ if (T) visit(T)； /* 訪問當前結點 */ preorder_recursive(T-lchild)； /* 訪問左子樹 */ preorder_recursive(T-rchild)； /* 訪問右子樹 */ b)非遞歸方式 void preorder_nonrecursive(Bitree T) /* 先序遍歷二叉樹的非遞歸算法 */ initstack(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 inorder_recursive(Bitree T) /* 中序遍歷二叉樹的遞歸算法 */ if (T) inorder_recursive(T-lchild)； /* 訪問左子樹 */ visit(T)； /* 訪問當前結點 */ inorder_recursive(T-rchild)； /* 訪問右子樹 */ b)非遞歸方式 void inorder_nonrecursive(Bitree T) initstack(S)； /* 初始化棧 */ push(S, T)； /* 根指針入棧 */ while (!stackempty(S) while (gettop(S, p) & p) /* 向左走到盡頭 */ push(S, p-lchild)； pop(S, p)； /* 空指針退棧 */ if (!stackempty(S) pop(S, p)； visit(p)； /* 訪問當前結點 */ push(S, p-rchild)； /* 向右走一步 */ 3)后序遍歷 a)遞歸方式 void postorder_recursive(Bitree T) /* 中序遍歷二叉樹的遞歸算法 */ if (T) postorder_recursive(T-lchild)； /* 訪問左子樹 */ postorder_recursive(T-rchild)； /* 訪問右子樹 */ visit(T)； /* 訪問當前結點 */ b)非遞歸方式 typedef struct BTNode* ptr； enum 0,1,2 mark； PMType； /* 有 mark 域的結點指針類型 */ void postorder_nonrecursive(BiTree T) /* 后續(xù)遍歷二叉樹的非遞歸算法 */ PMType a； initstack(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)； /* 訪問左子樹 */ break； case 1: push(S,a.ptr,2)； /* 修改 mark 域 */ if(a.ptr-rchild) push(S,a.ptr-rchild,0)； /* 訪問右子樹 */ break； case 2: visit(a.ptr)； /* 訪問結點 */ 三 、 實現遞歸與非遞歸的換轉原理和例子 原理分析 ： 通常 ,一個函數在調用另一個函數之前 ,要作如下的事情 :a)將實在參數 ,返回地址等信息傳遞給被調用函數保存 ； b)為被調用函數的局部變量分配存儲區(qū) ；c)將控制轉移到被調函數的入口 . 從被調用函數返回調用函數之前 ,也要做三件事情 :a)保存被調函數的計算結果 ；b)釋放被調函數的數據區(qū) ；c)依照被調函數保存的返回地址將控制轉移到調用函數 .所有 的這些 ,不論是變量還是地址 ,本質上來說都是 數據 ,都是保存在系統(tǒng)所分配的棧中的 . ok,到這里已經解決了第一個問題 :遞歸調用時數據都是保存在棧中的 ,有多少個數據需要保存就要設置多少個棧 ,而且最重要的一點是 :控制所有這些棧的棧頂指針都是相同的 ,否則無法實現同步 . 下面來解決第二個問題 :在非遞歸中 ,程序如何知道到底要轉移到哪個部分繼續(xù)執(zhí)行 ?回到上面說的樹的三種遍歷方式 ,抽象出來只有三種操作 :訪問當前結點 ,訪問左子樹 ,訪問右子樹 .這三種操作的順序不同 ,遍歷方式也不同 .如果我們再抽象一點 ,對這 三種操作再進行一個概括 ,可以得到 :a)訪問當前結點 :對目前的數據進行一些處理 ；b)訪問左子樹 :變換當前的數據以進行下一次處理 ；c)訪問右子樹 :再次變換當前的數據以進行下一次處理 (與訪問左子樹所不同的方式 ). 下面以先序遍歷來說明 : void preorder_recursive(Bitree T) /* 先序遍歷二叉樹的遞歸算法 */ if (T) visit(T)； /* 訪問當前結點 */ preorder_recursive(T-lchild)； /* 訪問左子樹 */ preorder_recursive(T-rchild)； /* 訪問右子樹 */ visit(T)這個操作就是對當前數據進行的處理 , preorder_recursive(T-lchild)就是把當前 數據變換為它的左子樹 ,訪問右子樹的操作可以同樣理解了 . 現在回到我們提出的第二個問題 :如何確定轉移到哪里繼續(xù)執(zhí)行 ?關鍵在于一下三個地方 :a)確定對當前數據的訪問順序 ,簡單一點說就是確定這個遞歸程序可以轉換為哪種方式遍歷的樹結構 ；b)確定這個遞歸函數轉換為遞歸調用樹時的分支是如何劃分的 ,即確定什么是這個遞歸調用樹的 左子樹 和 右子樹 c)確定這個遞歸調用樹何時返回 ,即確定什么結點是這個遞歸調用樹的 葉子結點 . 三個例子 好了上面的理論知識已經足夠了 ,下面讓我們看 看幾個例子 ,結合例子加深我們對問題的認識 .即使上面的理論你沒有完全明白 ,不要氣餒 ,對事物的認識總是曲折的 ,多看多想你一定可以明白 (事實上我也是花了兩個星期的時間才弄得比較明白得 ). 1.例子一 : f(n) = n + ； (n = 2)； 這個例子相對簡單一些 ,遞歸程序如下 : int f_recursive(int n) int u1, u2, f； if (n 2) f = n + 1； else u1 = f_recursive(int)(n/2)； u2 = f_recursive(int)(n/4)； f = u1 * u2； return f； 下面按照我們上面說的 ,確定好遞歸調用樹的結構 ,這一步是最重要的 .首先 ,什么是葉子結點 ,我們看到當 n = 0) switch(flagcp) case 0: /* 訪問的是根結點 */ if (stackcp = 2) /* 左子樹入棧 */ flagcp = 1； /* 修改標志域 */ cp+； stackcp = (int)(stackcp - 1 / 2)； flagcp = 0； else /* 否則為葉子結點 */ stackcp += 1； flagcp = 2； break； case 1: /* 訪問的是左子樹 */ if (stackcp = 2) /* 右子樹入棧 */ flagcp = 2； /* 修改標志域 */ cp += 2； stackcp = (int)(stackcp - 2 / 4)； flagcp = 1； else /* 否則為葉子結點 */ stackcp += 1； flagcp = 2； break； case 2: /* */ if (flagcp - 1 = 2) /* 當前是右子樹嗎 ? */ /* * 如 果是右子樹 , 那么對某一棵子樹的后序遍歷已經 * 結束 ,接下來就是對這棵子樹的根結點的訪問 */ stackcp - 2 = stackcp * stackcp - 1； flagcp - 2 = 2； cp = cp - 2； else /* 否則退回到后序遍歷的上一個結點 */ cp-； break； return stack0； 算法分析 :a)flag 只有三個可能值 :0 表示第一次訪問該結點 ,1 表示訪問的是左子樹 ,2表示 已經結束了對某一棵子樹的訪問 ,可能當前結點是這棵子樹的右子樹 ,也可能是葉子結點 .b)每遍歷到某個結點的時候 ,如果這個結點滿足葉子結點的條件 ,那么把它的 flag 域設為 2；否則根據訪問的是根結點 ,左子樹或是右子樹來設置 flag 域 ,以便決定下一次訪問該節(jié)點時的程序轉向 . 2.例子二 快速排序算法 遞歸算法如下 : 代碼 : void swap(int array, int low, int high) int temp； temp = arraylow； arraylow = arrayhigh； arrayhigh = temp； int partition(int array, int low, int high) int p； p = arraylow； while (low high) while (low = p) high-； swap(array,low,high)； while (low high & arraylow = p) low+； swap(array,low,high)； return low； void qsort_recursive(int array, int low, int high) int p； if(low high) p = partition(array, low, high)； qsort_recursive(array, low, p - 1)； qsort_recursive(array, p + 1, high)； 需要說明一下快速排序的算法 : partition 函數根據數組中的某一個數把數組劃分為兩個部分 ,左邊的部分均不大于這個 數 ,右邊的數均不小于這個數 ,然后再對左右兩邊的數組再進行劃分 .這里我們專注于遞歸與非遞歸的轉換 ,partition 函數在非遞歸函數中同樣的可以調用 (其實 partition 函數就是對當前結點的訪問 ). 再次進行遞歸調用樹和棧的分析 : 遞歸調用樹 :a)對當前結點的訪問是調用 partition函數 ；b)左子樹 :qsort_recursive(array, low, p - 1)；c)右子樹 :qsort_recursive(array, p +1, high)； d)葉子結點 :當 low high 時 ；e)可以看出這是一個先序調用的二叉樹 .棧 :要保存的數據是兩個表示范圍的坐標 . 代碼 : void qsort_nonrecursive(int array, int low, int high) int m50, n50, cp, p； /* 初始化棧和棧頂指針 */ cp = 0； m0 = low； n0 = high； while (mcp ncp) while (mcp 0) /* 壓棧 , 直到 m1cp = 0 */ while (n1cp 0) /* 壓棧 , 直到 n1cp = 0 */ cp+； m1cp = m1cp - 1； n1cp = n1cp - 1 - 1； /* 計算 akm(m - 1, 1),當 n = 0 時 */ m1cp = m1cp - 1； n1cp = 1； /* 改棧頂為 akm(m - 1, n + 1),當 m = 0 時 */ cp-； m1cp = m1cp - 1； n1cp = n1cp + 1 + 1； while (cp 0 | m1cp 0)； return n10 + 1； 四 、 遞歸程序的分類及用途 遞歸程序分為兩類 :尾部遞歸和非尾部遞歸 .上面提到的幾個例子都是非尾部遞歸 ,在一個選擇分支中有至少一個的遞歸調用 .相對而言 ,尾部遞歸就容易很多了 ,因為與非尾部遞歸相比 ,每個選擇分支只有一個遞歸調用 , 我們在解決的時候就不需要使用到棧 ,只要循環(huán)和設置好循環(huán)體就可以了 .下面再舉幾個尾部遞歸的例子吧 ,比較簡單我就不多說什么了 . 1.例子一 g(m, n) = 0 (m = 0, n = 0) = g(m - 1, 2n) + n； (m 0, n = 0) a)遞歸程序 int g_recursive(int m, int n) if (m = 0 & n = 0) return 0； return (g_recurse(m - 1, 2*n) + n)； b)非遞歸程序 int g_nonrecursive(int m, int n) int p； for (p = 0； m 0 & n = 0； m-, n *= 2) p += n； return p； 2.例子二 f(n) = n + 1 (n = 0) = n * f(n/2) (n 0) a)遞歸程序 int f_recursive(int n) if (n = 0) return 1； return (n * f_recurse(n/2)； b)非遞歸程序 int f_nonrecursive(int n) int m； for (m = 1； n 0； n /= 2) m *= n； return m+； 分析完了遞歸程序的分類 ,讓我們回頭看看在向非遞歸轉換的過程中用到了什么來實現轉換 : 1.循環(huán) ,因為程序要在某個條件下一直執(zhí)行下去 ,要代替遞歸程序 ,循環(huán)必不可少 ,對于尾部遞歸 ,循環(huán)結束的條件十分容易確定 ,只要按照不同分支的條件寫出來就可以了 .而對于非尾部遞歸程序 ,循環(huán)結束的條件一般是當棧為空時或者是結束了對遞歸調用樹的遍歷從樹的根結點退出時 ,而且有的時候寫成 while()的形式 ,有時寫成 do .while 的形式 (如上面的 akm 函數 ),具體怎樣 ,很難說清楚 ,取決于你對整個遞歸 程序的分析。 2.遞歸調用樹 ,樹的結構在轉換的過程中是不可見的 ,你不必為轉換專門寫一個樹結構 ,不過能不能把遞歸調用中的樹遍歷方式以及葉子結點 ,左子樹 ,右子樹等元素確定好是你能否正確解決問題的關鍵 (這一點已經在上面的分析過程中展露無疑 ),確定好這些后 ,剩下的工作大部分就是按照給出的幾種不同的遍歷樹的方式把程序進行改寫 ,這個過程就考驗你對樹結構還有遍歷方式是否很好的掌握了 (看出基礎的重要了嗎 ?如果回答是 ,那么和我一樣好好的打好基礎吧 ,一切都還不晚 !).對于尾部遞歸而言 ,可以看作沒有遞歸調用樹 ,所以尾 部遞歸的難度大大降低了。 3.棧 ,非尾部調用中需要棧來保存數據 ,這一點已經很清楚了 ,需要注意幾個問題 :a)棧有時可能會出現不夠的情況 ,拿上面的 akm函數來說 ,我用的 50個元素的數組 ,你如果把 m和n 值設置得大一些 ,這個棧就不能用了 ,有時你的算法正確了 ,不過沒有注意到這個問題還是會出錯的 ；反過來說 ,在遞歸調用中 ,系統(tǒng)或者編譯器的優(yōu)化功能不夠好的化 ,在這個棧上可能會消耗很多空間 ,這個時候如果你把程序改成非遞歸的形式 ,然后再用動態(tài)分配技術分配?？赡芫蜁殉绦虻男阅芴岣咭淮髩K -這也是我們學習這門技術的意義 之一 ,因為系統(tǒng)是機械化的 ,你如果知道更好的優(yōu)化辦法 ,為什么不用呢 ? 什么時候可以用遞歸解決問題 ?到了這一步 ,如果你對于上面說的已經相當明白的話 ,這個問題不難回答 ,如果我們要解決的問題要分成幾個小的部分 ,而其中的一些與你要解決的問題是一樣的 ,只不過是問題的規(guī)模 (如參數等 )小了 ,那么這樣的問題可以用遞歸來解決 .根據問題設計好一個遞歸是所有這些的基礎 ,轉換也是在原來的遞歸程序上進行的 ,所以這一步一定要做好 .通常 ,設計一個遞歸程序要注意一下幾個問題 :a)可以遞歸解決的問題是什么 ?b)入口和出口參數是什么 -即要明確好出入的接口。 說白了，遞歸程序是在對所要解決的問題進行數學上的分析后給出的，也就是說遞歸算法是從純數學的角度出 發(fā)考慮的，而非遞歸的算法則是在遞歸算法的基礎上考慮計算機內部處理遞歸程序的機制考慮來實現轉換的。任何一個遞歸算法，只要能夠準確的寫出遞歸調用樹的情況，分析清楚對當前結點的訪問操作是什么，左子樹右子樹是什么那么實現起遞歸和非遞歸的轉換就很輕松了。 參考文獻： 1 張益新 、 沈雁編 ： 算法導論 ， 國防科大出版社 。 2 嚴蔚敏 ： 數據結構 ， 清華大學出版社 。 3 徐孝凱：數據 結構，清華大學出版社 2006 年 9 月第 2 版。 Recursive algorithm design and conversion of non-recursive SUN Qing-Yu Ab