前言

會想要寫這篇是因為在碰到binary tree的時候會大量的使用recursion，因此想先瞭解Recursion的核心思維，希望能讓自己將遞迴的概念內化，讓他從此不再高不可攀。那我們就開始吧！首先，來聊聊基礎遞迴常見的思維方式之一，

  1. 先將一個大問題，拆解成幾個較小的問題
  2. 如果發現這些較小的問題當中，也能依照相同的方式拆解成更小的問題
  3. 每當小問題解決時，大問題也可以依靠小問題的結果來解決
  4. 從大問題到小問題，每層的解決方法都是一樣的，除了最小問題以外
  5. 根據以上幾點，我可以不段套用相同的函數，讓他自己幫自己解決問題

以上就是遞迴的基本核心精神，如何分析看不懂沒關係，我們先來看個最基本的例子

實戰範例

從 1 加到 n

如果使用迴圈的方式

1
2
3
4
5
def sum(n):
    result = 0
    for i in range(1, n+1):
        result += i
    return result

我們的思考方式如下：

  1. 大問題：從1加到n
  2. 小一點的問題：從1加到n-1
  3. 那我們只要先處理好小問題，最後再把其答案加上n就好了
1
2
def sum_1_to_n(x):
    return x + sum_1_to_n(x-1)

這個思維就是，如果我想算 sum(1~10)，我可以改成算 10 + sum(1~9)。那如何算 sum(1~9) 呢？當然就是 9 + sum(1~8) 依此類推下去。

但最後還有個小問題，如果我們要算 sum(1~1)，該怎麼做？如果寫成 1 + sum(1~0) 似乎有點不合理，所以這就是我們所謂的最小問題需要額外的處理，很幸運的是我們的最小問題非常容易，因為我們已經知道答案是 1。因此將上面的程式碼稍作修改後，最終答案如下：

1
2
3
4
def sum_1_to_n(x):
    if x == 1:
        return 1
    return x + sum_1_to_n(x-1)

到此為止，我們用兩種方法解決了相同的問題，而他們兩個思維本質上的差異在於：

  1. 迴圈（Iteration）：當用迴圈（Iteration）思考時，你則總是得很明確的告訴電腦每一個變數的值要如何改變，所以得想清楚這些值的所有變化過程。
  2. 遞迴（Recursion）：當用遞迴（Recursion）思考時，我們並不直接思考如何解決問題，而是先思考問題能否被拆小，還有大問題跟小問題間的關聯性。

迴圈應該對大多工程師來說都非常的直覺了，那我們為何還需要學遞迴的做法呢？以上述例子來說，Recursion雖然讓程式碼簡潔了一點點，不過思考起來稍微難了點，似乎有利有弊。但我們要把吃苦當吃補，這是因為這種思維的轉換，是遞迴最重要的地方，因為有些演算法，靠遞迴的思路來寫可能會非常容易，像是Binary Tree

重新用遞迴思維看一次上面的例子，當我們有了一個空殼的 function 如下

1
2
def sum_1_to_n(x):
    ???

我們並不清楚該如何實作他，但我想的是假如這個 function 可以運作，那我如何利用他自己來幫自己解決問題。於是我們想的東西是
從大到小問題

  1. 我發現一個轉移式 sum_1_to_n(x) = x+ sum_1_to_n(x-1)
  2. 那依此類推，sum_1_to_n(x-1) = (x-1) + sum_1_to_n(x-2) … 這個等式可以繼續無限循環下去。
  3. 而我也知道最小問題 sum_1_to_n(1) 的答案是 1，所以在最小問題可以停下直接給答案。
    從小問題到大問題
  4. 我知道 sum_1_to_n(1) 的答案是 1
  5. 那套用轉移式，我可以知道 sum_1_to_n(2) = 2 + sum_1_to_n(1) = 2 + 1 = 3，你會發現 x 就是 2 而 x-1 要放入 sum_1_to_n 函式裡面
  6. 繼續以上，我們可以知道 sum_1_to_n(3) = 3 + sum_1_to_n(2) = 3 + 3 = 6 … 如此循環下去，我就能知道任意的 sum_1_to_n(x) 的值了

河內塔


我們有三根柱子，並有 N 個圓盤套在最左邊柱子上面（上圖 N = 4），現在我們要把它們全部移動到最右邊的柱子上，請問我們最少需要移動幾次？
以下是移動的規則：

  1. 每次只能移動一個最上方的圓盤到任意柱子上
  2. 大圓盤不能放在小圓盤上面

遞迴思維：大問題沒頭緒的話，先想一下，如果能解決稍微小一點的問題，是不是就能靠他幫忙，來解決大問題了。

  1. 大問題：移動 4 個圓盤總共需要幾步
  2. 小一點的問題：移動 3 個圓盤總共需要幾步（相同的問題，但範圍變小）

假設我們知道小問題的答案（如何移動3個圓盤到特定柱子），我們可以把最後一步的步驟想成，假如移動3個盤子需要的步驟是K，那移動4個盤子就是

  1. 先移動3個盤子到中間的柱子，這個步驟需要K步
  2. 先把最下面的盤子移動到最右邊，這個步驟需要1步
  3. 然後把剩下的3個盤子從中間移動到右邊的柱子，這個步驟需要K步

1. 找到關係式

因此我們得到了一個寶貴的關係式：（移動 X 個盤子的步驟數）= 2 * (移動 X - 1 個盤子的步驟數) + 1

寫成程式碼的話就是：

1
2
def hanoi_tower_step(x):
    return 2 * hanoi_tower_step(x-1) + 1

2. 最小問題的解答

當然，一樣不能忘記，我們都會有一個”最小問題”，他不能再繼續遞迴下去，在這邊我們的最小問題，當然就是只有 1 個圓盤的時候該如何處理，而很顯然的，這個答案也是 1。最終我們就會得到非常簡潔的答案如下。

1
2
3
4
def hanoi_tower_step(x):
    if x == 1:
        return 1
    return 2 * hanoi_tower_step(x-1) + 1

靠著遞迴的思維，我們甚至根本就不知道移動盤子的最佳策略是什麼，或說我們唯一需要知道的策略，只有如何移動 1 個盤子，也就是 1 步，或 0 個盤子也行，就是 0 步，剩下的就只剩找到大小問題之間的關聯性就解決了，是不是很強大。

其他常見的簡單經典例子還有：階乘、費氏數列、輾轉相除法、爬梯子 等等。

費氏數列

以費氏數列（Fibonacci）為例

  1. 大問題：找到費氏數列中，第 X 個數的數值
  2. 小問題1：找到費氏數列中，第 X-1 個數的數值
  3. 小問題2：找到費氏數列中，第 X-2 個數的數值
  4. 大小問題的關聯式：fibonacci(x) = fibonacci(x-1) + fibonacci(x-2)
  5. 最小問題：第 1 個與第 2 個數的數值

所以程式碼，照抄下來就是:

1
2
3
4
def fibonacci(x):
    if x == 1 or x == 2:
        return 1
    return fibonacci(x-1) + fibonacci(x-2)

遞迴還有另一個小缺點是深度限制。簡單來說，就是遞迴的過程中，由於每個 function 都還沒執行完就又 call 了自己，那你就會堆積一堆執行到半路的 function，電腦需要一定的記憶體去記錄這些狀態，所以當你深度太超過就會炸掉（Stack Overflow），有興趣更深入理解的讀者可以看這邊的解說，常見的處理方式叫做 Tail Recursion。若以刷 Leetcode 題來說，由於題目會設計好，你幾乎是不會遇到這問題的，但實務中則要小心注意。

總結

思考的時候我們想三個方向

  1. 他們的大問題跟小問題分別可以是什麼
  2. 大小問題的關聯式子怎麼寫
  3. 最小問題又是什麼

Ref