前面課時中，我們完成了數據結構基礎知識的學習，從這一課時開始，我們將正式進入算法思維的學習。 不管是數據結構還是算法思維，它們的目標都是降低時間復雜度。數據結構是從數據組織形式的角度達成這個目標，而算法思維則是從數據處理的思路上去達成這個目標。 舉個例子，雖然你選擇了一個高效率的數據結構去處理問題，但如果數據處理的邏輯上出現缺陷，仍然會產生很多無效計算，造成時間浪費，那么我們該如何完善數據處理的邏輯？本課時，我們就來學習利用遞歸求解漢諾塔問題，以此來開啟算法思維的學習之路。 #### 什么是遞歸 在數學與計算機科學中，遞歸 （Recursion)）是指在函數的定義中使用函數自身的方法，直觀上來看，就是某個函數自己調用自己。 遞歸有兩層含義： 1. 遞歸問題必須可以分解為若干個規模較小、與原問題形式相同的子問題。并且這些子問題可以用完全相同的解題思路來解決； 2. 遞歸問題的演化過程是一個對原問題從大到小進行拆解的過程，并且會有一個明確的終點（臨界點）。一旦原問題到達了這個臨界點，就不用再往更小的問題上拆解了。最后，從這個臨界點開始，把小問題的答案按照原路返回，原問題便得以解決。 簡而言之，遞歸的基本思想就是把規模大的問題轉化為規模小的相同的子問題來解決。 在函數實現時，因為大問題和小問題是一樣的問題，因此大問題的解決方法和小問題的解決方法也是同一個方法。這就產生了函數調用它自身的情況，這也正是遞歸的定義所在。 格外重要的是，這個解決問題的函數必須有明確的結束條件，否則就會導致無限遞歸的情況。總結起來，遞歸的實現包含了兩個部分，一個是遞歸主體，另一個是終止條件。 #### 遞歸的算法思想 遞歸的數學模型其實就是數學歸納法，這個證明方法是我們高中時期解決數列問題最常用的方法。接下來，我們通過一道題目簡單回顧一下數學歸納法。 一個常見的題目是：證明當 n 等于任意一個自然數時某命題成立。 當采用數學歸納法時，證明分為以下 2 個步驟： 1. 證明當 n = 1 時命題成立； 2. 假設 n = m 時命題成立，那么嘗試推導出在 n = m + 1 時命題也成立。 與數學歸納法類似，當采用遞歸算法解決問題時，我們也需要圍繞這 2 個步驟去做文章： 1. 當你面對一個大規模問題時，如何把它分解為幾個小規模的同樣的問題； 2. 當你把問題通過多輪分解后，最終的結果，也就是終止條件如何定義。 所以當一個問題同時滿足以下 2 個條件時，就可以使用遞歸的方法求解： 1. 可以拆解為除了數據規模以外，求解思路完全相同的子問題； 2. 存在終止條件。 在我們講述樹結構時，曾經用過遞歸去實現樹的遍歷。接下來，我們圍繞中序遍歷，再來看看遞歸在其中的作用。 對樹中的任意結點來說，先中序遍歷它的左子樹，然后打印這個結點，最后中序遍歷它的右子樹。可見，中序遍歷是這樣的一個問題，如下圖所示：  當某個結點沒有左子樹和右子樹時，則直接打印結點，完成終止。由此可見，樹的中序遍歷完全滿足遞歸的兩個條件，因此可以通過遞歸實現。例如下面這棵樹：  當采用遞歸實現中序遍歷時，程序執行的邏輯架構如下圖所示：  其中，每個藍色的括號都是一次遞歸調用。代碼如下所示： ``` // 中序遍歷 public static void inOrderTraverse(Node node) { if (node == null) return; inOrderTraverse(node.left); System.out.print(node.data + " "); inOrderTraverse(node.right); } ``` 以上就是遞歸的算法思想。我們總結一下，寫出遞歸代碼的關鍵在于，寫出遞推公式和找出終止條件。 也就是說我們需要：首先找到將大問題分解成小問題的規律，并基于此寫出遞推公式；然后找出終止條件，就是當找到最簡單的問題時，如何寫出答案；最終將遞推公式和終止條件翻譯成實際代碼。 #### 遞歸的案例 下面我們通過一個古老而又經典的漢諾塔問題，幫助你理解復雜的遞歸問題。 漢諾塔問題是源于印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著 64 片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上，并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。 我們可以把這個問題抽象為一個數學問題。如下圖所示，從左到右有 x、y、z 三根柱子，其中 x 柱子上面有從小疊到大的 n 個圓盤。現要求將 x 柱子上的圓盤移到 z 柱子上去。要求是，每次只能移動一個盤子，且大盤子不能被放在小盤子上面。求移動的步驟。  我們來分析一下這個問題。這是一個大規模的復雜問題，如果要采用遞歸方法去解決的話，就要先把問題化簡。 我們的原問題是，把從小到大的 n 個盤子，從 x 移動到 z。 我們可以將這個大問題拆解為以下 3 個小問題： 1. 把從小到大的 n-1 個盤子，從 x 移動到 y； 2. 接著把最大的一個盤子，從 x 移動到 z； 3. 再把從小到大的 n-1 個盤子，從 y 移動到 z。 首先，我們來判斷它是否滿足遞歸的第一個條件。 其中，第 1 和第 3 個問題就是漢諾塔問題。這樣我們就完成了一次把大問題縮小為完全一樣的小規模問題。我們已經定義好了遞歸體，也就是滿足來遞歸的第一個條件。如下圖所示：  接下來我們來看判斷它是否滿足終止條件。隨著遞歸體不斷縮小范圍，漢諾塔問題由原來“移動從小到大的 n 個盤子”，縮小為“移動從小到大的 n-1 個盤子”，直到縮小為“移動從小到大的 1 個盤子”。移動從小到大的 1 個盤子，就是移動最小的那個盤子。根據規則可以發現，最小的盤子是可以自由移動的。因此，遞歸的第二個條件，終止條件，也是滿足的。 經過仔細分析可見，漢諾塔問題是完全可以用遞歸實現的。我們定義漢諾塔的遞歸函數為 hanio()。這個函數的輸入參數包括了： * 3 根柱子的標記 x、y、z； * 待移動的盤子數量 n。 具體代碼如下所示，在代碼中，hanio(n, x, y, z)，代表了把 n 個盤子由 x 移動到 z。根據分析，我們知道遞歸體包含 3 個步驟： 1. 把從小到大的 n-1 個盤子從 x 移動到 y，那么代碼就是 hanio(n-1, x, z, y)； 2. 再把最大的一個盤子從 x 移動到 z，那么直接完成一次移動的動作就可以了； 3. 再把從小到大的 n-1 個盤子從 y 移動到 z，那么代碼就是 hanio(n-1, y, x, z)。對于終止條件則需要判斷 n 的大小。如果 n 等于 1，那么同樣直接移動就可以了。 ``` public static void main(String[] args) { ? ? String x = "x"; ? ? String y = "y"; ? ? String z = "z"; ? ? hanio(3, x, y, z); } public void hanio(int n, String x, String y, String z) { ? ? if (n < 1) { ? ? ? ? System.out.println("漢諾塔的層數不能小于1"); ? ? } else if (n == 1) { ? ? ? ? System.out.println("移動: " + x + " -> " + z); ? ? ? ? return; ? ? } else { ? ? ? ? hanio(n - 1, x, z, y); ? ? ? ? System.out.println("移動: " + x + " -> " + z); ? ? ? ? hanio(n - 1, y, x, z); ? ? } } ``` **我們以 n = 3 為例，執行一下這段代碼**： 在主函數中，執行了 hanio(3, "x", "y", "z")。我們發現 3 比 1 要大，則進入遞歸體。分別先后執行了 hanio(2, "x", "z", "y")、"移動: x->z"、hanio(2, "y", "x", "z")。 其中的 hanio(2, "x", "z", "y")，又先后執行了 hanio(1, "x", "y", "z")、"移動: x->y"、hanio(1, "z", "x", "y")。在這里，hanio(1, "x", "y", "z") 的執行結果是 "移動: x->z"，hanio(1, "z", "x", "y")的執行結果是"移動: z->y"。 另一邊，hanio(2, "y", "x", "z") 則要先后執行 hanio(1, "y", "z", "x")、"移動: y->z"、hanio(1, "x", "y", "z")。在這里，hanio(1, "y", "z", "x") 的執行結果是"移動: y->x"，hanio(1, "x", "y", "z") 的執行結果是 "移動: x->z"。  最終梳理一下，代碼執行的結果就是： ``` 移動: x->z 移動: x->y 移動: z->y 移動: x->z 移動: y->x 移動: y->z 移動: x->z ``` 拋開用于處理輸入異常的代碼部分不談，它的代碼包含了 2 個部分： 1. 終止條件，即如何處理小規模的問題，實現的代碼量一定是很少的； 2. 遞歸體，即大問題向小問題分解的過程，實現的代碼量也不會太多。 因此，一個復雜問題的遞歸實現，通常代碼量都不會很多。 #### 總結 **遞歸的核心思想是把規模大的問題轉化為規模小的相似的子問題來解決**。 在函數實現時，因為解決大問題的方法和解決小問題的方法往往是同一個方法，所以就產生了函數調用它自身的情況。另外這個解決問題的函數必須有明顯的結束條件，這樣就不會產生無限遞歸的情況了。遞歸的應用非常廣泛，之后我們要講的很多數據結構和算法的編碼實現都要用到遞歸，例如分治策略、快速排序等等。 #### 練習題 下面，我們給出一道練習題，斐波那契數列。斐波那契數列是：0，1，1，2，3，5，8，13，21，34，55，89，144……。你會發現，這個數列中元素的性質是，某個數等于它前面兩個數的和；也就是 a[n+2] = a[n+1] + a[n]。至于起始兩個元素，則分別為 0 和 1。在這個數列中的數字，就被稱為斐波那契數。 現在的問題是，寫一個函數，輸入 x，輸出斐波那契數列中第 x 位的元素。例如，輸入 4，輸出 2；輸入 9，輸出 21。要求：需要用遞歸的方式來實現。我們會在后續實戰課程給出詳細答案。 最后，如果你在工作中，遇到了與遞歸相關的困難或經驗，歡迎你在留言區和我分享。