兩種「遞迴」：迭代式 vs. 真遞迴#

第 1 章說過，函式式編程用遞迴（recursion）取代賦值。但「遞迴」其實有兩種風貌，行為與限制完全不同：

  • 迭代（iteration）：遞迴呼叫位於函式末端，可被尾呼叫優化（TCO）轉成跳躍指令
  • 真遞迴（recursion）：遞迴呼叫不在末端，堆疊會持續成長

本章用 Clojure 把這兩種風貌講清楚。

迭代#

一個 Fibonacci 範例#

下面是用迭代風格產生前 n 個費氏數的 Clojure 程式：

(defn fibs-work [n i fs]
  (if (= i n)
    fs
    (fibs-work n (inc i) (conj fs (apply + (take-last 2 fs))))))

(defn fibs [n]
  (cond
    (< n 1) []
    (= n 1) [1]
    :else   (fibs-work n 2 [1 1])))

呼叫 (fibs 15) 會回傳：

[1 1 2 3 5 8 13 21 34 55 89 144 233 377 610]

極短的 Clojure 教學#

第一次看 Lisp 的人，常被滿屏的小括號弄到頭痛。其實只要學會這條對應關係：

  • C／C++／C#／Java：f(x);
  • Lisp：(f x)

Lisp 的語法真的就這麼簡單。Clojure 在此基礎上稍微豐富了一點，但核心仍是「所有東西都是 (函式 參數...)」。

拆解 fibs#

逐項看 fibs：

  • defn：定義一個新函式
  • 第一個函式叫 fibs，第二個叫 fibs-work
  • 函式名後的方括號是一個 vector（陣列），在這裡裝的是參數名

主體裡的 cond 像 switch，但會回傳值：

  • 接收一連串「述詞 / 值」的成對引數
  • 從上往下找到第一個為真的述詞，就回傳對應的值
  • (< n 1) 呼叫 < 函式，比較 n 與 1
  • (= n 1) 呼叫 = 函式，比較相等
  • :else 永遠為真，相當於 default 分支

主體解讀：

  • 若 n < 1：回傳 []
  • 若 n = 1：回傳 [1]
  • 否則：呼叫 (fibs-work n 2 [1 1])

拆解 fibs-work#

fibs-work 的三個參數：

  • n：要產生的費氏數個數
  • i：下一個要計算的索引
  • fs：目前累積的費氏數陣列

if 像 cond 的特例：(if p a b) 等同於 (cond p a :else b)。所以：

  • 若 (= i n)：回傳 fs
  • 否則：呼叫自己，把新的費氏數累加進去

關鍵函式：

  • conj：把元素附加到 vector 末端
  • take-last：取出 list 的最後 n 個元素
  • apply：把 list 攤開當作參數呼叫函式，例如 (apply + [3 4]) 等同於 (+ 3 4)

為什麼這是「迭代」#

注意 fibs-work 的遞迴呼叫位於函式末端——這是典型的尾呼叫（tail call）。語言可以用 TCO 把它轉換成 goto，等同純粹的迭代。

使用尾呼叫的函式，本質上就是迭代——堆疊不會無限成長。

TCO、Clojure 與 JVM#

Java 虛擬機（JVM）並不便於語言實作 TCO。事實上，前面的 fibs-work 在 Clojure 裡並未啟用 TCO，堆疊還是會逐次成長。要明確啟用 TCO，需用 recur：

(defn fibs-work [n i fs]
  (if (= i n)
    fs
    (recur n (inc i) (conj fs (apply + (take-last 2 fs))))))

recur 只能放在尾位置使用，效果是「重新呼叫包圍它的函式，但不增長堆疊」。

真遞迴#

費氏數其實有更自然優雅的寫法，直接照數學定義：

(defn fib [n]
  (cond
    (< n 1)  nil
    (<= n 2) 1
    :else    (+ (fib (dec n)) (fib (- n 2)))))

(defn fibs [n]
  (map fib (range 1 (inc n))))

fib(n) = fib(n−1) + fib(n−2) 一目瞭然。但是：

  • fib 的遞迴呼叫不在尾端——最後執行的是 +
  • 因此無法使用 recur，無法用 TCO
  • 堆疊會隨計算成長
  • 同一個 fib(k) 會被重複計算無數次

效能不忍卒睹#

fib 20 = 6765      Elapsed time:    1.459 msecs
fib 25 = 75025     Elapsed time:   11.735 msecs
fib 30 = 832040    Elapsed time:  106.490 msecs
fib 34 = 5702887   Elapsed time:  735.689 msecs

從成長速度推測這是 O(n³) 級別的演算法——再優雅也無法接受。

用迭代版本拯救效能#

(defn ifib
  ([n a b]
    (if (= 0 n)
      b
      (recur (dec n) b (+ a b))))
  ([n]
    (cond
      (< n 1)  nil
      (<= n 2) 1
      :else    (ifib (- n 2) 1 1))))

ifib 有兩個 arity overload，皆為迭代版本：

ifib 20 = 6765      Elapsed time: 0.185 msecs
ifib 25 = 75025     Elapsed time: 0.177 msecs
ifib 30 = 832040    Elapsed time: 0.146 msecs
ifib 34 = 5702887   Elapsed time: 0.148 msecs

效能大躍進，但失去了真遞迴版本的表達力。

用 memoize 同時取得優雅與效能#

回到引用透明性（referential transparency）：函式式語言中，給定相同輸入永遠得到相同輸出，所以從不需要重算。一旦算過 (fib 20)，記下結果即可。

(declare fib)

(defn fib-w [n]
  (cond
    (< n 1)  nil
    (<= n 2) 1
    :else    (+ (fib (dec n)) (fib (- n 2)))))

(def fib (memoize fib-w))

關鍵：

  • declare：先建一個未綁定的符號，待之後再定義它
  • memoize：拿一個函式 f，回傳一個包裝過的新函式 g；首次以 x 呼叫時會真正計算，往後同樣的 x 直接回傳記下的結果
fib 20 = 6765      Elapsed time: 0.168 msecs
fib 25 = 75025     Elapsed time: 0.162 msecs
fib 30 = 832040    Elapsed time: 0.151 msecs
fib 34 = 5702887   Elapsed time: 0.151 msecs

memoize 用少量記憶體換來巨大的速度提升。在引用透明的世界裡，這是「值得」的交換。

小結#

風格尾呼叫TCO 可用堆疊行為效能取捨
迭代有是不成長高效但較不直觀
真遞迴無否成長優雅但易超時
  • 迭代函式需以尾呼叫驅動，並依賴 TCO 防止堆疊爆掉
  • 真遞迴函式不使用尾呼叫、堆疊會成長，但配合 memoize 可避免效能崩潰
  • 兩種風格在幾乎所有函式式語言都有對應做法；非函式式語言也能模擬，但會犧牲不少優雅度
Backward 持久性資料 惰性求值 Forward