很多人都說遞迴，簡單來講就是函式自己叫自己，也有人說他很直觀好理解，但其實我當初理解起來挺困難的...

所以我們這裡先從數學的東西來開始理解，給定一個遞迴關係式 (Recurrence Relation)：

那這東西怎麼看呢？

• 上面那條式初始條件，我們現在稱 (1) 式
• 下面那個式每個東西跟前一個東西的關係 (像是 a3 跟 a2 的關係就是 a3 = a2+1)，我們現在稱 (2) 式

假設我現在想要知道 a3，那要怎麼得到？

我們可以先從 (2) 式開始看：

• n 代 3 的時候可以得到 a3 = a2 +1
• n 代 2 的時候可以得到 a2 = a1 +1
• n 代 1 的時候可以得到 a1 = a0 +1
• 再透過 (1) 式可以得到 a0 = 2
• 就可以得到 a1 = (2) + 1
• 再來得到 a2 = (2 + 1) + 1
• 再來得到 a3 = (2 + 1 + 1) + 1 = 5

那我們就可以得到我們的 a3 = 5 了！

那在現在將我們的 an 換成 f(n)

一樣把它分解可以得到：

• 求 f(3) 前要先求 f(2)
• 求 f(2) 前要先求 f(1)
• 求 f(0) 前要先求 f(0)
• 我們知道 f(0) 的值，所以就可以反推回去 f(3)

這裡的 f(n) 就很像我們的程式碼例如 python 的

def f(n):
    return

那我們就可以把剛剛的這個變成程式碼。

def f(n):
    # f(0) = 2
    if n == 0: 
        return 2
    
    # 下又叫了一次自己這個 f(n) 函式，所以前面會說自己叫自己
    # f(n) = f(n-1) +1
    return f(n-1) + 1 

這就是一個簡單的遞迴 (Recursion)！

像前面這種只跟自己前一項有關的我們可以叫做 一階線性遞迴關係式 (First-Order Linear Recurrence Relation)。

那肯定也有 二階遞迴關係式 (Second-Order Linear Recurrence Relation) 對吧？

沒錯！

二階遞迴關係式就是自己跟前兩項有關，常見的例子像是費波那契數，也有人稱作黃金分割數列，關係式如下。

程式碼就可以寫成：

def f(n):
    # f(0) = 0
    if n == 0: 
        return 0
    
    # f(1) = 1
    if n == 1:
        return 1
    
    # f(n) = f(n-1) + f(n-2)
    return f(n-1) + f(n-2)

河內塔 (Tower of Hanoi)

河內塔是一個經典的遞迴問題，規則如下：

1. 有三根柱子：通常稱為 A、B、C。
2. 有 n 個大小不一的盤子，最初按大小順序疊在柱子 A 上（小盤在上，大盤在下）。
3. 目標是將所有盤子移到柱子 C 上。
4. 規則限制：
   • 一次只能移動一個盤子。
   • 盤子只能放在空柱子上，或比它大的盤子上。

要怎麼以最少的步驟解決呢？

以下以兩個盤子為例移動

那當盤子有好幾個時要怎麼解呢？

以下我們以 5 個盤子來解釋

開始時可能會想說第一個盤子要怎麼動呢？

但其實我們可以反過來想，最後一盤子要怎麼動呢？

所以，我們先不看其他盤子，只看最後一個，那肯定就是 A -> C。

再來加上一個盤子，變兩個盤子後要怎麼移動？

那這不就跟前面兩個盤子的例子一樣嗎？

• 移動 1 次「1 個盤子」
• 移動 1 次「最後一個盤子」
• 移動 1 次「1 個盤子」

再加上一個盤子，變三個盤子之後後要怎麼移動？

我們先整理一些有用的資訊：

• 我們已經知道了最後一個盤子怎麼動。
• 我們知道了兩個盤子怎麼移動
• 根據遊戲規則「盤子只能放在空柱子上，或比它大的盤子上。」

所以要把最後一個盤子從 A 移到 C，其餘的盤子一定要在 B。

那現在就出現了一個小問題，其餘的盤子怎麼移到 B?

因為其餘的盤子只有兩個，所以就是兩個盤子的移動法，只是將 B、C 交換。

現在解決了「其餘的盤子怎麼移到 B?」，我們就能完成「最後一個盤子從 A 移到 C」。

再出現另外一個小問題「其餘在 B 的盤子怎麼移到 C?」，這裡又出現了兩個盤子的解決法。

最後完成了三個盤子的移動！且解法為：

• 移動 1 次「2 個盤子」
• 移動 1 次「最後一個盤子」
• 移動 1 次「2 個盤子」

再來再加一個變成四個盤子

那其實可以跟前面解決三個盤子的一樣，除了最後一個的都是其餘的盤子

那我們就會發現其餘盤子都可以視為一個整體。

這個四個盤子的大問題，就會變成解決「兩次其餘的盤子」的跟「最後一個盤子」的小問題

解法為：

• 移動 1 次「3 個盤子」
• 移動 1 次「最後一個盤子」
• 移動 1 次「3 個盤子」
  

現在我們在加一個變五個盤子

• 移動 1 次「4 個盤子」
• 移動 1 次「最後一個盤子」
• 移動 1 次「4 個盤子」

到這裡我們發現了一件事，n 個盤子的解法為：

• 移動 1 次「n - 1 個盤子」， A -> B
• 移動 1 次「最後一個盤子」， A -> C
• 移動 1 次「n - 1 個盤子」， B -> C

如果我們要知道 n 個盤子的最少的步驟就可以列出：

參考程式碼

def hanoi(n):
    if n == 1:
        return 1
    return 2 * hanoi(n - 1) + 1

如果我們想知道 n 個盤子在 A、B、C 柱的移動路徑就可以寫出：

def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"{source} -> {target}")
        return
    # A -> B
    hanoi(n-1, source, auxiliary, target)
    # A -> C
    hanoi(1, source, target, auxiliary)
    # B -> C
    hanoi(n-1, auxiliary, target, source)

# 將 3 個盤子從 A 移到 C
hanoi(3, 'A', 'C', 'B')

謝謝~