遞迴

學習內容：

• 遞迴的概念
• 費氏數列的遞迴實作
• 河內塔問題（Hanoi Tower）的遞迴解法

教學錄影

遞迴簡介

遞迴是一種函式自己呼叫自己的方法，適合用來解決可以拆解成子問題，而且子問題與原先問題相似的問題。遞迴函式通常需要一個終止條件（停止條件），避免無限迴圈。

先與一個簡單的例子：遞迴解 1 + 2 + ... + n。

假設 f(n) = 1 + ... + n，則 f(1) = 1，且當 n>1 時，f(n) = 1 + ... + n-1 + n = f(n-1) + n。

因此可以寫一個遞迴函式如下：

def recursive_sum(n):
    if n == 1:  # 終止條件
        return 1
    else:
        return n + recursive_sum(n - 1)  # 自己呼叫自己

# 測試
print(recursive_sum(5))  # 15

解釋：

• 當 n = 5 時，函式會呼叫自己：5 + recursive_sum(4)
• 依序拆解：5 + (4 + recursive_sum(3)) ... 直到 recursive_sum(1) 返回 1。

---

費氏數列（Fibonacci Sequence）

費氏數列的公式為： F(n) = F(n-1) + F(n-2)，其中 F(1) = 1, F(2) = 1。

程式碼：

def fibonacci(n):
    if n == 1 or n == 2:  # 基底條件
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

# 測試
for i in range(1, 8):
    print(f"F({i}) = {fibonacci(i)}")

輸出：

F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
F(6) = 8
F(7) = 13

---

河內塔問題（Tower of Hanoi）

問題描述：

• 有三根柱子（A、B、C），以及 n 個不同大小的圓盤，一開始圓盤全在 A 柱上。
• 每次只能移動一個圓盤，而且小圓盤必須永遠在大圓盤上面。
• 目標是將所有圓盤從 A 移到 C，並保持原本順序。

解題思路：

1. 如果只有一個圓盤的話，直接從 A 移動到 C 就可以了。

2. 如果有兩個圓盤的話，可使用以下解法：

   1. 先把第一個圓盤從 A 移動到 B， 
   2. 將第二個圓盤從 A 移動到 C，
   3. 最後將第一個圓盤從 B 移動到 C。

3. 假設我們已經知道如何解決 n-1 個圓盤的問題，則解決 n 個圓盤的方法如下：

   1. 先將 n-1 個圓盤從 A 移動到 B，
   2. 將第 n 個圓盤從 A 移動到 C，
   3. 最後將 n-1 個圓盤從 B 移動到 C。

程式碼：

def hanoi(n, source, target, auxiliary):
    if n == 1:  # 終止條件
        print(f"Move D1 from {source} to {target}")
    else:
        hanoi(n - 1, source, auxiliary, target)  # 將 n-1 個圓盤移到輔助柱
        print(f"Move D{n} from {source} to {target}")  # 將第 n 個圓盤移到目標柱
        hanoi(n - 1, auxiliary, target, source)  # 將 n-1 個圓盤從輔助柱移到目標柱

# 測試：n = 2 時
hanoi(2, 'A', 'C', 'B')

輸出：

Move D1 from A to B
Move D2 from A to C
Move D1 from B to C

練習

小明要爬 n 階樓梯，一次最多可以爬 3 階，請計算總共有多少種爬法。 （提示：第一次可能爬 1 階、2 階或 3 階）