當函數開始記住與遞迴：呼叫背後的機器

當函數開始「記住」與「自己呼叫自己」：你以為熟悉的呼叫，其實藏著一整座機器

在入門篇裡，我們把函數當成「輸入 → 處理 → 輸出」的黑盒子，把模組化當成「把大問題切小」的整理術。這些都對，但都還停在「函數是被你呼叫的工具」這個視角。

進階篇要換一個視角：函數在執行的當下，到底發生了什麼事？當一個函數還沒返回，就又呼叫了另一個函數（甚至呼叫自己），記憶體裡會長出什麼樣的結構？當函數「記得」上一次被呼叫時的狀態，它還算是純粹的工具嗎？而當我們把函數當成「值」傳來傳去，模組化又能進化成什麼樣子？

這篇文章假設你已經會寫函數、會傳參數、會 return。我們要往下挖一層，看看呼叫背後的呼叫堆疊（call stack）、閉包（closure）、高階函數（higher-order function）與遞迴（recursion），並用這些機制重新理解「模組化」的真正威力。

呼叫堆疊：每一次呼叫，都在堆一張紙

當你呼叫一個函數，直譯器或編譯器並不是「跳過去執行」就算了。它會在記憶體中一塊稱為堆疊（stack）的區域，壓入一張堆疊框（stack frame）——可以想像成一張便利貼，上面寫著：這個函數的區域變數、參數的值、以及「執行完要回到哪一行」的返回位址。

函數返回時，這張便利貼就被丟掉（彈出，pop），控制權回到上一張便利貼。所以堆疊的特性是後進先出（LIFO, Last In First Out）：最後被呼叫的函數，最先返回。

我們用一段簡單的程式碼觀察這個堆疊長什麼樣子：

def c():
    raise RuntimeError("看看我從哪裡被呼叫")

def b():
    c()

def a():
    b()

a()

執行後 Python 會印出 traceback：

Traceback (most recent call last):
  File "demo.py", line 10, in <module>
    a()
  File "demo.py", line 8, in a
    b()
  File "demo.py", line 5, in b
    c()
  File "demo.py", line 2, in c
    raise RuntimeError("看看我從哪裡被呼叫")
RuntimeError: 看看我從哪裡被呼叫

這段 traceback 其實就是呼叫堆疊由下往上的快照：最底層是 <module>（程式主體），往上依序是 a → b → c。你每次看到錯誤訊息，其實都在閱讀堆疊的內容。

這也解釋了一個入門時常被忽略的事實：區域變數之所以「區域」，是因為它住在堆疊框裡。函數一返回，框被彈出，變數就消失了。這不是規定，而是記憶體機制的自然結果。

看一個例子：堆疊深度是有限的

既然每次呼叫都要壓一張便利貼，那如果呼叫永遠不返回呢？堆疊會被塞爆。試試這段「沒有出口」的遞迴：

def dig(n):
    return dig(n + 1)   # 永遠呼叫自己，永遠不返回

dig(0)

執行結果：

RecursionError: maximum recursion depth exceeded

Python 預設把遞迴深度限制在約 1000 層（可用 sys.setrecursionlimit 調整，但別亂調），就是為了在堆疊真正撐爆作業系統的記憶體之前，先溫柔地喊停。C/C++ 這類沒有這層保護的語言，同樣的錯誤會直接觸發 stack overflow——這也正是知名問答網站名稱的由來。

遞迴：讓函數呼叫自己，把問題「縮小成自己」

理解了堆疊，遞迴就不再神祕。遞迴就是函數在自己的定義裡呼叫自己，每一層都把問題變得更小一點，直到小到不能再分（基底情形，base case），然後一層層返回、把結果組合回去。

寫對遞迴只要回答兩個問題：

1. 基底情形是什麼？（什麼時候停止，直接給答案）
2. 遞迴情形怎麼把問題縮小？（如何用「更小的自己」的答案組出現在的答案）

以階乘 $n! = n \times (n-1) \times \cdots \times 1$ 為例：

def factorial(n):
    if n <= 1:           # 基底情形
        return 1
    return n * factorial(n - 1)   # 遞迴情形：用 (n-1)! 組出 n!

呼叫 factorial(4) 時，堆疊會這樣堆起來再倒回去：

factorial(4) = 4 * factorial(3)
             = 4 * (3 * factorial(2))
             = 4 * (3 * (2 * factorial(1)))
             = 4 * (3 * (2 * 1))        ← factorial(1) 命中基底情形
             = 4 * (3 * 2)
             = 4 * 6
             = 24

注意：在 factorial(1) 返回之前，記憶體裡同時存在 4 張堆疊框。這就是遞迴的隱性成本——遞迴深度 = 堆疊空間消耗。

動手算一下：費氏數列與「重複計算」陷阱

遞迴寫起來優雅，但天真的寫法可能慢到離譜。看費氏數列 $F(n) = F(n-1) + F(n-2)$：

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

這段程式邏輯完全正確，但 fib(40) 會慢到讓你懷疑電腦壞了。問題在哪？畫出呼叫樹就懂了：fib(5) 會呼叫 fib(4) 和 fib(3)，而 fib(4) 又呼叫 fib(3) 和 fib(2)……同一個 fib(3) 被重複算了好幾次。整體呼叫次數約為 $O(2^n)$ ——指數爆炸。

解法是記憶化（memoization）：把算過的答案記下來，下次直接查表：

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

加上一行 @lru_cache 裝飾器，時間複雜度立刻從 $O(2^n)$ 降到 $O(n)$。同一個 fib(n) 只會真正計算一次，之後都是查快取。這個例子要傳達的重點是：遞迴的「對不對」和「快不快」是兩件事。寫對只需要基底情形 + 遞迴情形；寫快還要看有沒有重複子問題（這正是動態規劃，dynamic programming，的起點）。

閉包：讓函數「帶著記憶離開」

到目前為止，函數返回後它的區域變數就消失了。但有一種情況例外——閉包（closure）。

當你在一個函數裡定義另一個函數，而內層函數引用了外層函數的區域變數，這時就算外層函數已經返回，那些被引用的變數不會被銷毀，會被內層函數「打包帶走」。這個「函數 + 它所捕獲的環境」的組合，就叫閉包。

看一個經典的計數器：

def make_counter():
    count = 0
    def counter():
        nonlocal count    # 宣告要修改外層的 count，而非建立新的區域變數
        count += 1
        return count
    return counter

c1 = make_counter()
c2 = make_counter()

print(c1())   # 1
print(c1())   # 2
print(c1())   # 3
print(c2())   # 1  ← c2 有自己獨立的 count

make_counter 早就返回了，照理說它的 count 該消失，但 c1 還能持續記住並更新它。更妙的是 c1 和 c2 各自捕獲了獨立的 count——每次呼叫 make_counter 都會產生一份新的環境。

閉包的價值在於：它讓函數能封裝私有狀態，又不必動用整個類別（class）。在還沒有 class、或想要更輕量的場景，閉包是「帶狀態的函數」的最小單位。許多語言的事件處理器、回呼函數（callback）、裝飾器，骨子裡都是閉包。

看一個例子：用閉包做「乘法器工廠」

def multiplier(factor):
    def multiply(x):
        return x * factor    # factor 被閉包捕獲
    return multiply

double = multiplier(2)
triple = multiplier(3)

print(double(10))   # 20
print(triple(10))   # 30

multiplier 是一個「製造函數的函數」。double 和 triple 是兩個不同的函數，但它們共用同一份程式碼，差別只在各自捕獲的 factor。這正是模組化的進階形態：我們不再只是切分程式碼，而是用函數來生產函數，把「變動的部分」參數化、把「固定的邏輯」共用。

高階函數：把函數當成資料來傳遞

multiplier 回傳了一個函數；@lru_cache 接收了一個函數。能夠接收函數作為參數或回傳函數作為結果的函數，就叫高階函數（higher-order function）。

這背後是一個觀念上的躍升：函數是「一等公民」（first-class citizen）——它和整數、字串一樣是值，可以存進變數、放進串列、當參數傳遞、當結果返回。

這讓模組化跨出全新一步。傳統模組化是「把行為封裝起來」，高階函數則是「把行為當參數傳進去」。看排序就懂了：

students = [
    {"name": "小明", "score": 85},
    {"name": "小華", "score": 92},
    {"name": "小美", "score": 78},
]

# 把「如何取出排序依據」這個行為，當函數傳給 sorted
by_score = sorted(students, key=lambda s: s["score"], reverse=True)
by_name  = sorted(students, key=lambda s: s["name"])

sorted 本身不知道你要按什麼排序，它把「取出排序鍵」這段邏輯外包給你傳進去的 key 函數。同一個 sorted，配上不同的 key，就能應付無數種排序需求——這就是高階函數帶來的彈性。lambda 則是「匿名函數」的語法糖，適合寫這種用過即丟的小函數。

map、filter、reduce 是高階函數的三大經典：

from functools import reduce

nums = [1, 2, 3, 4, 5]

squared = list(map(lambda x: x ** 2, nums))          # [1, 4, 9, 16, 25]
evens   = list(filter(lambda x: x % 2 == 0, nums))   # [2, 4]
total   = reduce(lambda acc, x: acc + x, nums, 0)    # 15

它們的共通精神是：把「對每個元素做什麼」這件事，從「如何走訪集合」中抽離出來。走訪的骨架被 map/filter/reduce 共用，變動的行為由你以函數注入。這種「骨架固定、行為注入」的設計，正是許多框架（framework）的核心——框架替你寫好流程的骨架，留下幾個「鉤子（hook）」讓你傳入函數來客製。

純函數與副作用：模組化能不能「拼裝」的關鍵

我們把函數切得很細、傳來傳去，但有個前提常被忽略：這些函數能不能安全地組合？答案取決於它們有沒有副作用（side effect）。

純函數（pure function）滿足兩個條件：

1. 相同輸入永遠得到相同輸出（不依賴外部狀態）。
2. 不修改外部任何東西（不改全域變數、不寫檔、不印出、不改傳入的可變物件）。

# 純函數：只看輸入，只回傳結果
def add_tax(price, rate):
    return price * (1 + rate)

# 非純函數：依賴並修改外部狀態
total = 0
def add_to_total(x):
    global total
    total += x          # 副作用：改了外部的 total
    return total

純函數有一個對模組化極為珍貴的性質：可組合、可測試、可快取、可平行化。因為它不依賴也不影響外界，你可以放心把它和別的純函數串接，順序與環境都不影響結果。前面 lru_cache 能安全快取 fib，正因為 fib 是純函數——同樣的 n 永遠回傳同樣的值，快取才不會出錯。

這不代表副作用是壞事——印出畫面、寫入資料庫、讀取感測器，本來就是程式存在的目的。重點是把純邏輯和副作用分開：核心計算寫成純函數，副作用集中在邊界處理。這樣你的核心邏輯好測、好重用，而難以預測的部分被收斂到少數幾個地方。這正是現代函數式風格給模組化的最大啟發。

重點回顧

• 呼叫堆疊是函數呼叫的物理基礎：每次呼叫壓入一張堆疊框（區域變數 + 返回位址），返回時彈出。Traceback 就是堆疊的快照，遞迴太深會撐爆堆疊。
• 遞迴只需「基底情形 + 遞迴情形」兩件事就能寫對，但寫對不等於寫快——有重複子問題時要用記憶化，可把費氏數列從 $O(2^n)$ 降到 $O(n)$。
• 閉包讓內層函數帶走外層的變數，使函數能封裝私有狀態，是「帶記憶的函數」的最小單位。
• 高階函數把函數當成值來傳遞與回傳；map/filter/sorted(key=...) 都靠「骨架固定、行為注入」帶來巨大彈性。
• 純函數（無副作用）可組合、可測試、可快取、可平行化；把純邏輯與副作用分離，是進階模組化的核心心法。

深入探討（研究所視角）

尾呼叫最佳化（Tail Call Optimization, TCO）與堆疊。 遞迴受限於堆疊深度，但若遞迴呼叫是函數的最後一個動作（尾呼叫，tail call），理論上不需要保留當前堆疊框——因為返回後沒有其他事要做。支援 TCO 的語言（如 Scheme、部分 functional 語言實作）會把尾遞迴重用同一張堆疊框，使其在 $O(1)$ 空間執行，等價於迴圈。值得注意的是 CPython 刻意不實作 TCO（Guido van Rossum 公開表態，理由是會破壞 traceback 的可讀性與除錯體驗）。因此在 Python 中,深遞迴演算法常需手動改寫成迴圈 + 顯式堆疊（explicit stack），這也是「遞迴與迭代在計算能力上等價」這一定理的工程體現。

閉包的實作：變數捕獲的兩種語意。 閉包捕獲外層變數時，有「按值捕獲（capture by value）」與「按參考捕獲（capture by reference）」之分。Python 採後者——閉包捕獲的是變數本身而非當下的值，這導致經典陷阱：在迴圈中建立的多個閉包，會共享同一個迴圈變數，全部讀到迴圈結束後的最終值。

funcs = [lambda: i for i in range(3)]
print([f() for f in funcs])   # [2, 2, 2] 而非 [0, 1, 2]！

修正方式是用預設參數強制在定義當下「快照」該值：lambda i=i: i。底層機制上,CPython 用 cell 物件包裝被捕獲的自由變數（free variable），可透過 function.__closure__ 檢視。理解這點，你才能解釋為何 nonlocal 是必要的，以及為何 C++ lambda 需要明確寫出 [=]（按值）或 [&]（按參考）捕獲清單。

λ 演算：函數作為計算的最小模型。 高階函數與閉包並非語言設計者的巧思，而是 1930 年代 Alonzo Church 提出的 λ 演算（lambda calculus）的直接後裔。λ 演算只有三種東西：變數、函數抽象（abstraction，即 $\lambda x.M$）、函數應用（application）。令人震撼的是，這套僅以「函數」為唯一基本元素的系統，被證明與圖靈機（Turing machine）計算能力等價（Church–Turing thesis）——也就是說，凡是可計算的，都能只用函數表達。連自然數、布林值、遞迴都能用純函數編碼（例如以 Church numerals 表示整數、以 Y combinator 在無名函數中實現遞迴）。當你寫下一個 lambda、傳遞一個高階函數，你其實正站在整個計算理論的地基上：模組化的終極形式，就是把世界拆解成可組合的函數。