遞迴思維：用河內塔理解函數呼叫自身

什麼是遞迴？

遞迴（Recursion）是函數「呼叫自身」的程式設計技巧。它必須有：

1. 基礎情況（Base Case）：何時停止遞迴
2. 遞迴呼叫（Recursive Call）：以更小的問題呼叫自身
3. 問題縮小（Reduction）：確保每次呼叫都趨近基礎情況

---

河內塔的遞迴解

目標：把 n 個圓盤從 A 柱移到 C 柱，每次只能移動一個，大盤不能放在小盤上。

思路分三步：

• 把 n-1 個盤從 A 移到 B（用 C 當中繼）
• 把最大盤從 A 移到 C
• 把 n-1 個盤從 B 移到 C（用 A 當中繼）

def hanoi(n, from_rod, to_rod, via_rod):
    if n == 1:  # Base case
        print(f"Move disk 1: {from_rod} -> {to_rod}")
        return

    hanoi(n - 1, from_rod, via_rod, to_rod)  # Step 1
    print(f"Move disk {n}: {from_rod} -> {to_rod}")  # Step 2
    hanoi(n - 1, via_rod, to_rod, from_rod)  # Step 3

hanoi(3, 'A', 'C', 'B')
# Move disk 1: A -> C
# Move disk 2: A -> B
# Move disk 1: C -> B
# Move disk 3: A -> C
# Move disk 1: B -> A
# Move disk 2: B -> C
# Move disk 1: A -> C

---

時間複雜度

最少步數 = 2^n - 1。

• 3 個盤：7 步
• 10 個盤：1023 步
• 64 個盤：18,446,744,073,709,551,615 步（約 5800 億年！）

---

呼叫堆疊視覺化

遞迴的核心是「函數在記憶體中疊加呼叫」，每次呼叫都在堆疊（Stack）上新增一層。

hanoi(3, A, C, B)
  hanoi(2, A, B, C)
    hanoi(1, A, C, B) → 印出 "Move disk 1: A -> C"
    印出 "Move disk 2: A -> B"
    hanoi(1, C, B, A) → 印出 "Move disk 1: C -> B"
  印出 "Move disk 3: A -> C"
  hanoi(2, B, C, A)
    ...

前往互動河內塔遊戲，用拖放操作親自驗證！