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

遞迴（Recursion）是函數呼叫自身的程式設計技巧

什麼是遞迴？

一個合法的遞迴必須包含三個要素：

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

Python 程式碼

def hanoi(n, from_rod, to_rod, via_rod):
    if n == 1:                          # 基礎情況
        print(f"移動圓盤 1：{from_rod} → {to_rod}")
        return

    hanoi(n - 1, from_rod, via_rod, to_rod)   # 步驟 1
    print(f"移動圓盤 {n}：{from_rod} → {to_rod}")  # 步驟 2
    hanoi(n - 1, via_rod, to_rod, from_rod)   # 步驟 3

hanoi(3, 'A', 'C', 'B')
# 移動圓盤 1：A → C    (共 7 步)
# 移動圓盤 2：A → B
# 移動圓盤 1：C → B
# 移動圓盤 3：A → C
# 移動圓盤 1：B → A
# 移動圓盤 2：B → C
# 移動圓盤 1：A → C

時間複雜度：最少步數 = 2ⁿ − 1