一文讀懂遞迴演演算法

（點選上方公眾號，可快速關註）

轉自：劉毅

https://www.61mon.com/index.php/archives/208/

好文投稿， 請點選 → 這裡瞭解詳情

遞迴的學習絕對是一個持久戰，沒有人可以一蹴而就。一年兩年的，很尋常。

問題的複雜，加上遞迴本身的細節，我們想要 “學會”，”學好”，再 “用好”，是需要一個漫長的過程的。所以還希望讀者有足夠的耐心。

一：什麼是遞迴

所謂遞迴，簡單點來說，就是一個函式直接或間接呼叫自身的一種方法，它通常把一個大型複雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解。

我們可以把” 遞迴 “比喻成 “查字典 “，當你查一個詞，發現這個詞的解釋中某個詞仍然不懂，於是你開始查這第二個詞。

可惜，第二個詞裡仍然有不懂的詞，於是查第三個詞，這樣查下去，直到有一個詞的解釋是你完全能看懂的，那麼遞迴走到了盡頭，然後你開始後退，逐個明白之前查過的每一個詞，最終，你明白了最開始那個詞的意思。（摘自知乎的一個回答）

我們以階乘作為：

int Factorial(int n){    

      if (n == 0)  return 1;  

      return

      n * Factorial(n – 1);

}

二：遞迴與棧的關係

常常聽到 “遞迴的過程就是出入棧的過程”，這句話怎麼理解？我們以上述程式碼為例，取 n=3

” role=”presentation” style=”box-sizing: border-box; outline: 0px; display: inline-block; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border-width: 0px; border-style: initial; border-color: initial;” tabindex=”0″>n=3，則過程如下：

• 第 1~4 步，都是入棧過程，Factorial(3)呼叫了Factorial(2)，Factorial(2)又接著呼叫Factorial(1)，直到Factorial(0)；

• 第 5 步，因 0 是遞迴結束條件，故不再入棧，此時棧高度為 4，即為我們平時所說的遞迴深度；

• 第 6~9 步，Factorial(0)做完，出棧，而Factorial(0)做完意味著Factorial(1)也做完，同樣進行出棧，重覆下去，直到所有的都出棧完畢，遞迴結束。

每一個遞迴程式都可以把它改寫為非遞迴版本。我們只需利用棧，透過入棧和出棧兩個操作就可以模擬遞迴的過程，二叉樹的遍歷無疑是這方面的代表。

但是並不是每個遞迴程式都是那麼容易被改寫為非遞迴的。某些遞迴程式比較複雜，其入棧和出棧非常繁瑣，給編碼帶來了很大難度，而且易讀性極差，所以條件允許的情況下，推薦使用遞迴。

三：如何思考遞迴




在初學遞迴的時候, 看到一個遞迴實現, 我們總是難免陷入不停的驗證之中，比如上面提及的階乘，求解Factorial(n)時，我們總會情不自禁的發問，Factorial(n-1)可以求出正確的答案麼？接著我們就會再用Factorial(n-2)去驗證，，，不停地往下驗證直到Factorial(0)。

對遞迴這樣的不適應，和我們平時習慣的思維方式有關。我們習慣的思維是：已知Factorial(0)，乘上 1 就等於Factorial(1)，再乘以 2 就等於Factorial(2)，，，直到乘到 n。

而遞迴和我們的思維方式正好相反。

那我們怎麼判斷這個遞迴計算是否是正確的呢？Paul Graham 提到一種方法，如下：

如果下麵這兩點是成立的，我們就知道這個遞迴對於所有的 n 都是正確的。

1. 當 n=0,1​

   ” role=”presentation” style=”box-sizing: border-box; outline: 0px; display: inline-block; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border-width: 0px; border-style: initial; border-color: initial;” tabindex=”0″>n=0,1 時，結果正確；

2. 假設遞迴對於 n

   ” role=”presentation” style=”box-sizing: border-box; outline: 0px; display: inline-block; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border-width: 0px; border-style: initial; border-color: initial;” tabindex=”0″>n 是正確的，同時對於 n+1

   ” role=”presentation” style=”box-sizing: border-box; outline: 0px; display: inline-block; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border-width: 0px; border-style: initial; border-color: initial;” tabindex=”0″>n+1 也正確。

這種方法很像數學歸納法，也是遞迴正確的思考方式，上述的第 1 點稱為基本情況，第 2 點稱為通用情況。

在遞迴中，我們通常把第 1 點稱為終止條件，因為這樣更容易理解，其作用就是終止遞迴，防止遞迴無限地執行下去。

下麵我們用兩個例子來具體說明這種數學歸納法：

例 1 漢諾塔展開目錄

問題描述為：有三根桿子 A，B，C。A 桿上有 N 個穿孔圓盤，盤的尺寸由上到下依次變大，B，C 桿為空。要求按下列規則將所有圓盤移至 C 桿：

1. 每次只能移動一個圓盤；

2. 大盤不能疊在小盤上面。

問：如何移？最少要移動多少次？

首先看下基本情況，即終止條件：N=1 時，直接從 A 移到 C。

再來看下通用情況：當有 N 個圓盤在 A 上，我們已經找到辦法將其移到 C 槓上了，我們怎麼移動 N+1 個圓盤到 C 槓上呢？很簡單，我們首先用將 N 個圓盤移動到 C 上的方法將 N 個圓盤都移動到 B 上，然後再把第 N+1 個圓盤（最後一個）移動到 C 上，再用同樣的方法將在 B 槓上的 N 個圓盤移動到 C 上，問題解決。

程式碼如下：

void Hanoi(int n, char a, char b, char c){    //終止條件

    if (n == 1)

    {

         cout <a <“–>” <c <endl;        

         return;

    }    //通用情況

    Hanoi(n – 1, a, c, b);

    Hanoi(1, a, b, c);

    Hanoi(n – 1, b, a, c);

}

例 2 求二叉樹節點個數展開目錄

首先看下基本情況，即終止條件：當為空樹時，節點數為 0；

再來看下通用情況：當前節點的左，右子樹節點數都被求出，則以當前結點為根的二叉樹的節點總數就是 “左子樹 + 右子樹 + 1”。

程式碼如下：

int GetNodes(Node * node){    //終止條件

    if (node == nullptr)

      return 0;    //通用情況

    return

      GetNodes(node->left) + GetNode(node->right) + 1;

}

四：什麼時候該用遞迴

當我們遇到一個問題時，我們是怎麼判斷該題用遞迴來解決的？

問題可用遞迴來解決需具備的條件：

1. 子問題需與原問題為同樣的事，且規模更小；

2. 程式停止條件。

覺得本文有幫助？請分享給更多人

關註「演演算法愛好者」，修煉程式設計內功

淘口令：複製以下紅色內容，再開啟手淘即可購買

範品社，使用￥極客T恤￥搶先預覽（長按複製整段文案，開啟手機淘寶即可進入活動內容）

近期，北京地區正常發貨，但派件時間有所延長。