（06）遞歸程序構造 · 十八年開發經驗分享

這次談談遞歸程序的問題，之所以選遞歸這個話題主要是以下三個原因。第一個是自己的體會。在我的記憶中掌握遞歸程序是有一定難度的。最初在寫遞歸程序時是全靠腦子想，一層一層的想著程序如何遞歸下去，然后又是如何返回的，最后整個遞歸程序又是如何結束的。對于一些簡單的遞歸問題，特別是一些簡單的習題，這個作法雖然笨拙，但是卻有著相當的實用價值。只要腦子好使，一層一層的想下去，是可以解決一部分問題的。但是對于一些邏輯有點復雜，或者遞歸層數比較多的情況，這個方法就不好用了。尤其是在一些遞歸深度不確定的情況下，單憑腦子想就很難解決問題了。? 第二個是應該有相當一部分的開發者認為遞歸程序不好寫。這個結論來源于我的一個員工。這個員工大概有幾年的開發經驗，并且談吐處事很得體穩重，給我的印象是不錯的。在一次閑談中他將會寫遞歸程序作為一個亮點提出來的，言下之意自己的技術是很不錯的。另一次經驗來自一個面試的人。他把項目組的頭會寫遞歸程序作為一個敬佩的理由。由此我判斷應該有相當一部分的開發者覺得遞歸程序不好寫。? 第三個理由就比較簡單了，那就是遞歸程序確實很有用，很值得去掌握。? **一．遞歸的定義** 遞歸的概念的嚴格定義應該是來自數學，這個google一下就可以知道的。當然數學上的定義肯定是不太好理解的，有興趣的可以自己看一下。這里給一個比較容易理解的版本，也是一個比較實用的說法。如果定義一個概念的時候使用到了這個概念本身那么這就是遞歸了。比如下面的二叉樹的定義：二叉樹(BinaryTree)是：n(n≥0)個結點的有限集，它或者是空集(n=0)，或者由一個根結點及兩棵互不相交的、分別稱作這個根的左子樹和右子樹的二叉樹組成。在上面的文字中，冒號后面的內容就是二叉樹的定義。在這個定義中又出現了二叉樹這個概念，所以這是二叉樹的遞歸定義。當然需要區分一下這和循環論證是不一樣的。 **二．遞歸程序的結構** 既然憑腦子想不能很好的解決問題，那么我們就需要使用一個更好的方法。我們可以從遞歸程序的結構出發來構造完成遞歸程序。所以這里介紹一下遞歸程序的結構。從結構上講遞歸程序分為三個部分：遞歸出口，邏輯處理，遞歸調用。 1. 遞歸的出口所謂遞歸的出口，就是指滿足什么條件時程序不再需要遞歸調用了。這個時候往往是遞歸程序遞歸調用到最深層的時候，需要開始回歸了。還有一種情況是做出判斷決定是否執行當前的遞歸程序，比如對遞歸方法的參數的容錯處理。 2. 邏輯處理在考慮寫遞歸程序的時候，至少需要知道在遞歸出口時需要執行的邏輯處理是什么。其次就是某一次遞歸調用前后需要執行的邏輯處理是什么。需要注意的是，這個時候的處理只是針對部分的數據，因為都是在某一次遞歸的執行中處理數據。不是對所有數據的完整的處理。完整的處理是整個遞歸程序執行完畢后才能完成的。 3. 遞歸調用這個很好理解，就是在遞歸程序內部調用自己。 **三．遞歸程序構造舉例1** 為了有一個感性的認識，這里舉一個例子說明一下如何從遞歸程序的結構出發來完成遞歸程序的構造。這里就用教科書上遍歷二叉樹的例子來分析一下如何處理遞歸程序。首先我們考慮一下如果我們需要遍歷一顆二叉樹，那么什么情況下我們可以不用再遞歸遍歷或者沒必要繼續遍歷了？這個答案就是遇到一顆空樹的時候就沒有必要再遍歷了。參考下面的方法定義： ~~~ public void VisitBinaryTree(NODE node) { … } ~~~ 其中參數node就表示了一顆二叉樹的根節點，如果這個node的值是空的話，那么我們就沒有必要再遞歸了，可以按照需求直接處理或者什么都不做直接返回了。所以上述方法的內部需要包含如下代碼來結束遞歸，也就是所謂的遞歸的出口： ~~~ public void VisitBinaryTree(NODE node) { if (node == null) return; … } ~~~ 至此已經完成遞歸程序的第一部分了，當然也是最簡單的一部分。需要強調的是這部分雖然是最簡單的，但還是建議大家在構思遞歸程序時最好首先明確這部分的內容。否則一個遞歸程序沒有出口的話，那么運行起來會把棧擊穿的，從而導致崩潰。下面第二步就要考慮核心的問題了，那就是如果node不為空時我們如何處理？首先需要明確我們要完成的邏輯是什么。一般教科書上的遍歷例子，不會講所謂邏輯處理的，只是描述遍歷，這里我們可以假設一個虛擬的邏輯處理。我們假設這個邏輯處理由如下的方法完成： ~~~ public void DoSomething(NODEnode) { … } ~~~ 于是加上邏輯執行部分，我們的遞歸程序看上去就如同下面的樣子了： ~~~ public void VisitBinaryTree(NODE node) { if (node == null) return; DoSomething(node); } ~~~ 很明顯Dosomething按照既定的要求完成了對節點node的處理，但是我們需要處理二叉樹中的每一個節點，只執行DoSomething(node)這一行代碼是不夠的。所以這時我們需要遞歸程序的第三部分，即遞歸調用。就這個例子而言，node表示一棵二叉樹的根節點，并且在VisitBinaryTree方法內部我們調用了DoSomething方法完成了對node節點的處理。那么剩下的工作就是要處理node的左子樹和右子樹了，只有這樣才算是完成了對node為根的整棵二叉樹的處理。這個時候我們可以再繼續寫代碼來處理node的左子樹和右子樹，但是等等，由于我們現在構造的方法VisitBinaryTree就是用來處理二叉樹的，而左子樹或者右子樹本身也是一棵二叉樹，所以我們就沒有必要再寫額外的代碼來處理而是直接遞歸調用該方法就可以了。所以加入遞歸調用的代碼后，VisitBinaryTree方法差不多就是下面的樣子了： ~~~ public void VisitBinaryTree(NODE node) { if (node == null) return; DoSomething(node); VisitBinaryTree(node.LeftSon); VisitBinaryTree(node.RightSon); } ~~~ 至此遍歷二叉樹的方法就完成了。下面我們來討論一個細節問題，那就是根節點的判空問題。在這個例子中node的判空處理既是遞歸的出口，也是一種容錯處理。因為如果不進行容錯處理的話，那么DoSomething方法內容如果訪問了node對象的屬性或者方法，就會出現null對象方法的異常。但是有些人更習慣于在遞歸執行前對是否為空值作出判斷，從而決定是否遞歸調用，這可以保證每次遞歸調用時，傳入的值都不為空。因此代碼差不多是下面這個樣子： ~~~ public void VisitBinaryTree(NODE node) { DoSomething(node); if (node.LeftSon != null) VisitBinaryTree(node.LeftSon); if (node. RightSon != null) VisitBinaryTree(node.RightSon); } ~~~ 這樣的代碼確實保證了傳入遞歸方法的根節點參數不為空。但是卻忽略了一個問題，那就是第一次調用VisitBinaryTree方法時node為空的情況沒有考慮。假設如下的情況，我們在一個方法OneMethod中如下調用的例子： ~~~ public void OneMethod(…) { … VisitBinaryTree(null); … } ~~~ 所以為了應對這個情況，最初判斷node是否為空的代碼還是需要的，這樣代碼就變成如下的樣子了： ~~~ public void VisitBinaryTree(NODE node) { if (node == null) return; DoSomething(node); if (node.LeftSon != null) VisitBinaryTree(node.LeftSon); if (node. RightSon != null) VisitBinaryTree(node.RightSon); } ~~~ 好，現在重點來了。上面的代碼中最后兩個判空的if語句還需要么？答案是不需要了。假設去掉最后兩個判空的判斷，那么傳入的參數確實有可能為空，但是當這樣的參數傳入VisitBinaryTree方法時，該方法的最開始就對這個參數執行了判空的處理，如果為空就直接返回了。所以達到了同樣的目的。請體會一下，遞歸程序就是這個樣子的。 **四．遞歸程序構造舉例2** 在數據結構的教材上，遍歷二叉樹的方法有六種不同的版本，最常用的只有三種，分別是：先序優先遍歷，左序優先遍歷，右序優先遍歷。上面的例子是用的先序優先遍歷。下面看看用同樣的方法來構造左序優先遍歷的遞歸方法。所謂左序優先，是要求先遍歷處理完二叉樹的左子樹，然后處理根節點，然后再遍歷處理完二叉樹的右子樹。好，我們還是首先考慮遞歸的出口，對于遍歷二叉樹而言，其出口仍舊不變，還是判空，如果為空就直接返回不處理了。所以第一步的代碼是一樣的，就不再列出來了。下面是如果節點不為空，我們需要先遍歷處理左子樹，再處理根節點，然后再遍歷處理右子樹。根據這個要求我們明確了可以執行的邏輯是處理根節點。至此，第二部分完成一半了，列出代碼如下： ~~~ public void VisitBinaryTree(NODE node) { if (node == null) return; DoSomething(node); } ~~~ 下面就是關鍵了，那就是如何遞歸調用了。為了易于理解，我們可以先假設，需要處理的二叉樹是沒有任何左子樹的，也就是說要么沒有任何子樹，要么就只有右子樹。這樣我們只需要考慮右子樹就可以了，把左子樹忘了吧。根據遍歷處理的要求是先處理根節點然后再處理左子樹，所以我們的代碼如下： ~~~ public void VisitBinaryTree(NODE node) { if (node == null) return; DoSomething(node); VisitBinaryTree(node.RightSon); } ~~~ 當VisitBinaryTree被遞歸調用時，傳入的是node的右子樹的根節點。這個右子樹根節點，傳入后首先是被判空，然后是調用DoSomething執行邏輯處理，然后再次遞歸調用來處理右子樹的右子樹。顯然這樣的遞歸調用邏輯是對的。現在再假設需要處理的二叉樹是沒有任何右子樹的，也就是說要么沒有任何子樹，要么就只有左子樹。這樣我們只需要考慮左子樹就可以了，這次可以把右子樹忘了吧。根據遍歷處理的要求是先處理左子樹然后再根節點，所以我們的代碼如下： ~~~ public void VisitBinaryTree(NODE node) { if (node == null) return; VisitBinaryTree(node.LeftSon); DoSomething(node); } ~~~ 當VisitBinaryTree被遞歸調用時，傳入的是node的左子樹的根節點。這個左子樹根節點，傳入后首先是被判空，然后是再次遞歸調用VisitBinaryTree遍歷處理左子樹的左子樹。然后再處理根節點，顯然這樣的邏輯也是對的。好了，至此我們可以考慮既有左子樹又有右子樹的一般情況了，把兩部分的代碼合起來就可以了，如下所示： ~~~ public void VisitBinaryTree(NODE node) { if (node == null) return; VisitBinaryTree(node.LeftSon); DoSomething(node); VisitBinaryTree(node.RightSon); } ~~~ **五．遞歸程序構造的比較** 舉例1的構造過程是從遞歸程序結構本身直接推導出來的，是一個很自然的過程。在構造時并沒有考慮是否為后續遍歷，只是構造完成后正好和后續遍歷一致。在舉例2中的構造過程中使用了一點技巧，那就是為了簡化問題，看清遞歸調用的位置，先后假設不存在左子樹和右子樹的情況，然后再將兩部分合并，從而完成遞歸程序的構造。這就是說舉例2中在使用這個方法時多了一個簡化問題的步驟，這是使用已知的知識解決問題的一個例子。關于解決問題的更多討論可以參考本系列中問題解決篇的討論。再將這兩個例子和教科書上的例子做一個比較。這里的討論給出了遞歸程序構造的詳細步驟，相比教科書上直接給出結果來說，我覺得這里討論更容易理解。另一個區別是，由于本文的例子是從遞歸的結構出發完成構造遞歸程序的，所以沒有涉及討論所謂遞歸程序執行時會用到的工作棧的問題。有興趣的可以再看一下其它相關的資料，對工作棧的了解應該多少對遞歸程序的認識是有幫助的。這次就寫到這里，感謝閱讀。下一篇還是談談遞歸程序，介紹一個更強更"廣譜適用"的方法來完成遞歸程序的設計。