這篇談談遞歸程序設計的問題。從取名上來說是想刻意區別內容的側重點不同。上一篇是構造，其重點是從遞歸程序的自身結構出發，試圖用一種比較直觀的方法來完成遞歸程序的構造。這篇的重點是設計，其中的區別在于，這次是從問題本身的結構出發來完成遞歸程序的開發任務。上一篇中介紹的方法，比較簡單直觀，八股文的意味非常濃郁，并且還有一個比較大的缺點，那就是在實際使用時往往會受制與方法本身而不能解決有一定難度的問題。實際上遞歸是一種客觀存在的現象，遞歸的描述問題是對客觀世界的一種認識。本文從對問題的認識，描述和分析這些步驟來介紹一下如何完成遞歸程序的設計。 **一．問題的描述方法—巴克斯范式** 在我上大學的時候，巴克斯范式出現在編譯原理的課程中，是用來定義文法的。在數據結構課程中并沒有介紹巴克斯范式。但是在實踐中發現，這個范式對完成遞歸程序非常有幫助。因為根據巴克斯范式，我們可以自動生成詞法分析程序，而這些程序就包含了各種遞歸程序及其調用。這里不打算從編譯的角度來介紹巴克斯范式，而是借用巴克思范式的思想來幫助完成遞歸程序的開發。所以規范和嚴謹程度是遠不如巴克斯范式的。? 先從一個具體的例子開始引入巴克斯范式。現將前一篇“遞歸程序構造”中關于二叉樹的定義再次描述如下： n(n≥0)個結點的有限集，它或者是空集(n=0)，或者由一個根結點及兩棵互不相交的、分別稱作這個根的左子樹和右子樹的二叉樹組成。這是一個用嚴謹的自然語言描述的定義，下面用另一種形式等價的來描述這個定義： ~~~ <二叉樹> = null | 節點<左子樹><右子樹> <左子樹> = <二叉樹> <右子樹> = <二叉樹> ~~~ 上面的定義由三行文本組成，每一行文本是一個等式，稱之為規則，所以一共是三條規則。等號的左邊稱為非終結符，等號的右邊表示這個非終結符的組成內容。一般非終結符用“<”和“>”兩個符號包圍。這些是巴克斯范式中的內容。 以第一條規則為例，等號的右邊首先是null，這表示空，這等效于二叉樹定義中的“它或者是空集(n=0)”這段文字。最右邊的“節點<左子樹><右子樹>”表示二叉樹有一個節點及其所屬的左子樹和右子樹組成，這個描述二叉樹概念中的“由一個根結點及兩棵互不相交的、分別稱作這個根的左子樹和右子樹”這些文字對應。第二條和第三條規則表示左子樹和右子樹都是一棵二叉樹，這個和定義中的最后幾個字“二叉樹組成”相對應。最后看一下第一條規則中的字符“|”。這個字符在巴克斯范式中表示或，其含義是該字符的左邊或者右邊只能取一個。這個符號和定義中“或者”這個詞相對應。至此可以確認上述三條規則對二叉樹的描述和定義對二叉樹的描述是等價的。 有了這個等價的巴克斯范式版本的二叉樹定義，我們就可以使用處理巴克斯范式的方式，或者說可以使用編譯原理中詞法分析的思路來完成遞歸程序的開發了。 **二．從規則集轉換得到遞歸程序** 前一篇遞歸程序構造中使用了遍歷二叉樹的例子，這里還是使用相同的例子，看看從規則集是如何完成遍歷二叉樹的遞歸程序的開發的。事實上從規則集合轉換得到遞歸程序的步驟是很簡單的，也是可以自動化的。我們完全可以開發一個程序，通過掃描規則集自動生成遞歸程序。下面介紹手工完成的具體步驟。 首先為每一個非終結符定義方法，每一個方法只用來處理對應的非終結符。上述三條規則中包含了三個非終結符，所以我們需要三個方法，列出如下： 現在我們得到了三個方法，然后給這些方法定義參數。由于三個方法都是需要遍歷，所以二叉樹的根節點必須是方法的參數，否則遍歷無法完成。增加參數后方法如下所示： ~~~ // 對應非終結符<二叉樹>，表示遍歷二叉樹 VisitBinaryTree() // 對應非終結符<左子樹>，表示遍歷左子樹 VisitLeftBinaryTree() // 對應非終結符<右子樹>，表示遍歷右子樹 VisitRightBinaryTree() ~~~ 第二步是在各個方法中對指定的非終結符的右邊內容進行處理。首先看第一條規則。由于規則中有一個“|”符號，表示右邊兩部分內容不能同時處理，所以顯然需要一個if語句做判斷，然后分情況分別處理兩部分的內容。先看“|”左邊的內容null，這個含義是二叉樹為空，如果是這樣，那么就無需遍歷，所以對應的代碼應該如下： ~~~ if (node == null) ? ? return; ~~~ 如果二叉樹不為空，那么需要處理“|”右邊的內容，這些內容分別是根節點，左子樹和右子樹。對于根節點的處理可以抽象的使用一個方法ProcessNode來表示，而后面的左子樹和右子樹是非終結符，可以直接調用處理改非終結符的方法就可以了。修改完后代碼如下所示： ~~~ if (node == null) ? ? return; else { ?ProcessNode(node); ?VisitLeftBinaryTree(node.LeftTree); ?VisitRightBinaryTree(node.RightTree); } ~~~ 對于第二和第三條規則，由于右邊只有一個非終結符，所以其內部的代碼就是直接調用對應的處理該非終結符的方法就可以了，完整的代碼如下所示： ~~~ public void VisitBinaryTree(Nodenode) { ? if (node == null) ? ? ? return; ? else ? { ? ? ? ProcessNode(node); ? ? ? VisitLeftBinaryTree(node.LeftTree); ? ? ? VisitRightBinaryTree(node.RightTree); ? } } public voidVisitLeftBinaryTree(Node node) { ? VisitBinaryTree(node); } public voidVisitRightBinaryTree(Node node) { ? VisitBinaryTree(node); } ~~~ 到這里代碼就完成了，而且還是一個間接遞歸的版本。下面對這些規則和代碼再做一個討論，讓問題更明晰透徹一些。 **三．若干細節討論** 第一個需要討論的就是間接遞歸的問題。我們熟知的遍歷二叉樹的遞歸程序都是直接遞歸，這里得到卻是一個間接遞歸。其原因不是介紹的方法有問題，而是上述規則的設計問題。可以看到第二條和第三條規則表達含義就是<左子樹>和<右子樹>也是一棵二叉樹。補充這個規則的用意是為了體現二叉樹定義中出現的文字“分別稱作這個根的左子樹和右子樹的二叉樹組成”，這句話表明左子樹和右子樹也是二叉樹，所以加入了上述規則。 既然非終結符<左子樹>，<右子樹>和非終結符<二叉樹>是等價的，那么我們可以將規則一右邊出現的<左子樹>，<右子樹>直接用<二叉樹>代替。這樣規則一就如下所示： <二叉樹> = null | 根節點<二叉樹><二叉樹>。還是使用相同的推導方法，這次我們可以得到直接遞歸版本的二叉樹遍歷程序，如下所示： ~~~ public void VisitBinaryTree(Nodenode) { ? if (node == null) ? ? ? return; ? else ? { ? ? ? ProcessNode(node); ? ? ? VisitBinaryTree(node.LeftTree); ? ? ? VisitBinaryTree(node.RightTree); ? } } ~~~ 第二點是需要強調一下推導的步驟。我相信有些讀者已經發現了間接遞歸的問題，并且也能夠直接修改代碼，將其改為直接遞歸。比如直接通過讀代碼就可以發現方法VisitLeftBinaryTree和VisitRightBinaryTree什么都沒干，只是調用了方法VisitBinaryTree，所以就可以直接調用VisitBinaryTree從而替換掉對方法VisitLeftBinaryTree和VisitRightBinaryTree的調用。這樣做是可以的，尤其在這個具體的簡單問題上。但是當規則足夠多，并且足夠復雜時問題就不太可能如此直白，如此易于觀察并得到結論。所以強烈推薦的做法是先修改規則，然后再根據規則推導出程序，這是工程化的做法。 第三點，不是需要給所有的非終結符都定義方法，然后再重構，如果能看清問題那么可以直接寫出最終的代碼。這也是不太規范的一個地方。 第四點是強調一下這里用到的規則和巴克斯范式的差異。前文已經提到巴克斯范式是一個規范而嚴謹的定義，而這里使用的規則只是借用了巴克斯范式的思路來描述問題，不是很規范和嚴謹。比如在巴克斯范式中規則一的右邊不僅表示<二叉樹>可以由根節點，<左子樹>和<右子樹>組成，同時也表示這三者先后出現順序。但是這里使用的規則，僅僅表示組成內容。或者說僅僅想表示二叉樹的結構，從而和二叉樹定義的描述等價。注意二叉樹定義中的描述沒有規定左子樹和右子樹出現的先后順序。所以在VisitBinaryTree方法中對處理內容的先后沒有限制。由此可以推導出遍歷二叉樹的不同版本，只需要改變調用處理非終結符方法的先后順序即可。 當然根據具體的問題，可以給規則加入其它的變化和含義，以便于等價的描述問題。這其中的取舍和尺度的把握是體現問題分析和程序設計能力的地方。下面再舉一個例子來說明這個問題。 **四．規則的設計** 從前文的介紹可以看出，只要得到了規則，那么推導出遞歸程序是非常容易的。 這樣開發遞歸程序的問題就轉化為如何得到規則了，也就是規則的設計問題。我的建議是多練習，多實踐。因為沒有一個固定的做法可以讓我們比較容易的得到規則集，所以通過練習和實踐來提升問題的分析能力和程序的設計能力就是關鍵和捷徑了。但是在有些時候思考問題的技巧對我們也是有輔助幫助作用的。這里舉一個例子來說明一下，想以此擴展一下讀者的思路。這個例子是：逆轉字符串。 如何逆轉一個字符串是非常容易的，但是如何寫出遞歸版本的代碼呢？請注意寫出遞歸的關鍵是發現問題的遞歸結構，這個遞歸結構是事物本身的特性，而不是只指我們需要對該事物執行什么樣的操作。這就是說逆轉操作不是關鍵，關鍵是如何找到字符串的遞歸結構或者說如何找到字符串的遞歸定義。當然這個能力需要在實踐中逐步培養。下面直接給出規則版本的定義： ~~~ <字符串> = null | <字符> | <字符><字符串><字符> <字符> = … ~~~ 先看第一條規則的右邊，null表示空串，<字符>表示只有一個字符的字符串，最后部分表示有多個字符的字符串。第二條規則定義了<字符>可以是哪些字符，比如’a’,’b’,’c’或者’1’,’2’，’3’，之類的，由于比較多就不全寫了。然后使用上文介紹的方法來推導，首先給<字符串>定義方法，然后分別處理右邊的內容，代碼如下所示： ~~~ public string ReverseString(stringstr, int start, int end) { ? if (start >= end) ? ? ? return str; ? else if (str == null || str.Length < 1) ? ? ? return str; ? else if (str.Length == 1) ? ? ? return str; ? else ? { ? ? ? char temp = str[start]; ? ? ? str[start] = str[end]; ? ? ? str[end] = temp; ? ? ? return ReverseString(str, start + 1, end - 1); ? } } ~~~ 方法的調用如下： ~~~ ReverseString(str, 0,str.Length - 1); ~~~ ReverseString中的第一個if是加入的遞歸出口判斷，這不能從規則推導出來，需要自己加。關于遞歸的出口可以閱讀前一篇：遞歸程序構造。另外還可以修改規則如下： ~~~ <字符串> = null | <字符> | <字符><字符串> <字符> = … ~~~ 依據這個規則也是可以推出遞歸程序的。 關于遞歸程序還有一些話題可以講，比如數學歸納法，遞推，遞歸程序的測試等等。這些擴展的話題留在以后再介紹了，這次就寫到這里了。最后推廣一下我的群244054966，歡迎正在創業的程序員加入。入群時請寫明“csdn博文”，否則不加。