十八年開發經驗分享（07）遞歸程式設計

這篇談談遞歸程式設計的問題。從取名上來說是想刻意差別内容的側重點不同。上一篇是構造，其重點是從遞歸程式的自身結構出發，試圖用一種比較直覺的方法來完成遞歸程式的構造。這篇的重點是設計，其中的差別在于，這次是從問題本身的結構出發來完成遞歸程式的開發任務。上一篇中介紹的方法，比較簡單直覺，八股文的意味非常濃郁，并且還有一個比較大的缺點，那就是在實際使用時往往會受制與方法本身而不能解決有一定難度的問題。實際上遞歸是一種客觀存在的現象，遞歸的描述問題是對客觀世界的一種認識。本文從對問題的認識，描述和分析這些步驟來介紹一下如何完成遞歸程式的設計。

一．問題的描述方法—巴克斯範式

在我上大學的時候，巴克斯範式出現在編譯原理的課程中，是用來定義文法的。在資料結構課程中并沒有介紹巴克斯範式。但是在實踐中發現，這個範式對完成遞歸程式非常有幫助。因為根據巴克斯範式，我們可以自動生成詞法分析程式，而這些程式就包含了各種遞歸程式及其調用。這裡不打算從編譯的角度來介紹巴克斯範式，而是借用巴克思範式的思想來幫助完成遞歸程式的開發。是以規範和嚴謹程度是遠不如巴克斯範式的。

先從一個具體的例子開始引入巴克斯範式。現将前一篇“遞歸程式構造”中關于二叉樹的定義再次描述如下：

n(n≥0)個結點的有限集，它或者是空集(n=0)，或者由一個根結點及兩棵互不相交的、分别稱作這個根的左子樹和右子樹的二叉樹組成。

這是一個用嚴謹的自然語言描述的定義，下面用另一種形式等價的來描述這個定義：

<二叉樹> = null |

節點<左子樹><右子樹>

<左子樹> = <二叉樹>

<右子樹> =

<二叉樹>

上面的定義由三行文本組成，每一行文本是一個等式，稱之為規則，是以一共是三條規則。等号的左邊稱為非終結符，等号的右邊表示這個非終結符的組成内容。一般非終結符用“<”和“>”兩個符号包圍。這些是巴克斯範式中的内容。

以第一條規則為例，等号的右邊首先是null，這表示空，這等效于二叉樹定義中的“它或者是空集(n=0)”這段文字。最右邊的“節點<左子樹><右子樹>”表示二叉樹有一個節點及其所屬的左子樹和右子樹組成，這個描述二叉樹概念中的“由一個根結點及兩棵互不相交的、分别稱作這個根的左子樹和右子樹”這些文字對應。第二條和第三條規則表示左子樹和右子樹都是一棵二叉樹，這個和定義中的最後幾個字“二叉樹組成”相對應。最後看一下第一條規則中的字元“|”。這個字元在巴克斯範式中表示或，其含義是該字元的左邊或者右邊隻能取一個。這個符号和定義中“或者”這個詞相對應。至此可以确認上述三條規則對二叉樹的描述和定義對二叉樹的描述是等價的。

有了這個等價的巴克斯範式版本的二叉樹定義，我們就可以使用處理巴克斯範式的方式，或者說可以使用編譯原理中詞法分析的思路來完成遞歸程式的開發了。

二． 從規則集轉換得到遞歸程式

前一篇遞歸程式構造中使用了周遊二叉樹的例子，這裡還是使用相同的例子，看看從規則集是如何完成周遊二叉樹的遞歸程式的開發的。事實上從規則集合轉換得到遞歸程式的步驟是很簡單的，也是可以自動化的。我們完全可以開發一個程式，通過掃描規則集自動生成遞歸程式。下面介紹手工完成的具體步驟。

首先為每一個非終結符定義方法，每一個方法隻用來處理對應的非終結符。上述三條規則中包含了三個非終結符，是以我們需要三個方法，列出如下：

// 對應非終結符<二叉樹>，表示周遊二叉樹

visitbinarytree()

//

對應非終結符<左子樹>，表示周遊左子樹

visitleftbinarytree()

對應非終結符<右子樹>，表示周遊右子樹

visitrightbinarytree()

現在我們得到了三個方法，然後給這些方法定義參數。由于三個方法都是需要周遊，是以二叉樹的根節點必須是方法的參數，否則周遊無法完成。增加參數後方法如下所示：

node是二叉樹的根節點

visitbinarytree(node node)

node是左子樹的根節點

visitleftbinarytree(node node)

node是右子樹的根節點

visitrightbinarytree(node node)

第二步是在各個方法中對指定的非終結符的右邊内容進行處理。首先看第一條規則。由于規則中有一個“|”符号，表示右邊兩部分内容不能同時處理，是以顯然需要一個if語句做判斷，然後分情況分别處理兩部分的内容。先看“|”左邊的内容null，這個含義是二叉樹為空，如果是這樣，那麼就無需周遊，是以對應的代碼應該如下：

如果二叉樹不為空，那麼需要處理“|”右邊的内容，這些内容分别是根節點，左子樹和右子樹。對于根節點的處理可以抽象的使用一個方法processnode來表示，而後面的左子樹和右子樹是非終結符，可以直接調用處理改非終結符的方法就可以了。修改完後代碼如下所示：

對于第二和第三條規則，由于右邊隻有一個非終結符，是以其内部的代碼就是直接調用對應的處理該非終結符的方法就可以了，完整的代碼如下所示：

到這裡代碼就完成了，而且還是一個間接遞歸的版本。下面對這些規則和代碼再做一個讨論，讓問題更明晰透徹一些。

三．

若幹細節讨論

第一個需要讨論的就是間接遞歸的問題。我們熟知的周遊二叉樹的遞歸程式都是直接遞歸，這裡得到卻是一個間接遞歸。其原因不是介紹的方法有問題，而是上述規則的設計問題。可以看到第二條和第三條規則表達含義就是<左子樹>和<右子樹>也是一棵二叉樹。補充這個規則的用意是為了展現二叉樹定義中出現的文字“分别稱作這個根的左子樹和右子樹的二叉樹組成”，這句話表明左子樹和右子樹也是二叉樹，是以加入了上述規則。

既然非終結符<左子樹>，<右子樹>和非終結符<二叉樹>是等價的，那麼我們可以将規則一右邊出現的<左子樹>，<右子樹>直接用<二叉樹>代替。這樣規則一就如下所示：

= null | 根節點<二叉樹><二叉樹>

還是使用相同的推導方法，這次我們可以得到直接遞歸版本的二叉樹周遊程式，如下所示：

第二點是需要強調一下推導的步驟。我相信有些讀者已經發現了間接遞歸的問題，并且也能夠直接修改代碼，将其改為直接遞歸。比如直接通過讀代碼就可以發現方法visitleftbinarytree和visitrightbinarytree什麼都沒幹，隻是調用了方法visitbinarytree，是以就可以直接調用visitbinarytree進而替換掉對方法visitleftbinarytree和visitrightbinarytree的調用。這樣做是可以的，尤其在這個具體的簡單問題上。但是當規則足夠多，并且足夠複雜時問題就不太可能如此直白，如此易于觀察并得到結論。是以強烈推薦的做法是先修改規則，然後再根據規則推導出程式，這是工程化的做法。

第三點，不是需要給所有的非終結符都定義方法，然後再重構，如果能看清問題那麼可以直接寫出最終的代碼。這也是不太規範的一個地方。

第四點是強調一下這裡用到的規則和巴克斯範式的差異。前文已經提到巴克斯範式是一個規範而嚴謹的定義，而這裡使用的規則隻是借用了巴克斯範式的思路來描述問題，不是很規範和嚴謹。比如在巴克斯範式中規則一的右邊不僅表示<二叉樹>可以由根節點，<左子樹>和<右子樹>組成，同時也表示這三者先後出現順序。但是這裡使用的規則，僅僅表示組成内容。或者說僅僅想表示二叉樹的結構，進而和二叉樹定義的描述等價。注意二叉樹定義中的描述沒有規定左子樹和右子樹出現的先後順序。是以在visitbinarytree方法中對處理内容的先後沒有限制。由此可以推導出周遊二叉樹的不同版本，隻需要改變調用處理非終結符方法的先後順序即可。

當然根據具體的問題，可以給規則加入其它的變化和含義，以便于等價的描述問題。這其中的取舍和尺度的把握是展現問題分析和程式設計能力的地方。下面再舉一個例子來說明這個問題。

四．

規則的設計

從前文的介紹可以看出，隻要得到了規則，那麼推導出遞歸程式是非常容易的。

這樣開發遞歸程式的問題就轉化為如何得到規則了，也就是規則的設計問題。我的建議是多練習，多實踐。因為沒有一個固定的做法可以讓我們比較容易的得到規則集，是以通過練習和實踐來提升問題的分析能力和程式的設計能力就是關鍵和捷徑了。但是在有些時候思考問題的技巧對我們也是有輔助幫助作用的。這裡舉一個例子來說明一下，想以此擴充一下讀者的思路。這個例子是：逆轉字元串。

如何逆轉一個字元串是非常容易的，但是如何寫出遞歸版本的代碼呢？請注意寫出遞歸的關鍵是發現問題的遞歸結構，這個遞歸結構是事物本身的特性，而不是隻指我們需要對該事物執行什麼樣的操作。這就是說逆轉操作不是關鍵，關鍵是如何找到字元串的遞歸結構或者說如何找到字元串的遞歸定義。當然這個能力需要在實踐中逐漸培養。下面直接給出規則版本的定義：

<字元串> = null | <字元> |

<字元><字元串><字元>

<字元> = …

先看第一條規則的右邊，null表示空串，<字元>表示隻有一個字元的字元串，最後部分表示有多個字元的字元串。第二條規則定義了<字元>可以是哪些字元，比如’a’,’b’,’c’或者’1’,’2’，’3’，之類的，由于比較多就不全寫了。然後使用上文介紹的方法來推導，首先給<字元串>定義方法，然後分别處理右邊的内容，代碼如下所示：

方法的調用如下：

reversestring(str, 0, str.length -

1);

reversestring中的第一個if是加入的遞歸出口判斷，這不能從規則推導出來，需要自己加。關于遞歸的出口可以閱讀前一篇：遞歸程式構造。另外還可以修改規則如下：

<字元串>

= null | <字元> | <字元><字元串>

<字元> =

…

依據這個規則也是可以推出遞歸程式的。

關于遞歸程式還有一些話題可以講，比如數學歸納法，遞推，遞歸程式的測試等等。這些擴充的話題留在以後再介紹了，這次就寫到這裡了。最後推廣一下我的群244054966，歡迎正在創業的程式員加入。入群時請寫明“csdn博文”，否則不加。