質因數分解

開場問題#

函式式編程是否優於用可變變數的傳統寫法？本章用一個熟悉的小練習——質因數分解（Prime Factors）——分別以 Java 與 Clojure 透過 TDD 推導，做出第一輪比較。

Java 版本#

從最退化的測試出發#

public class PrimeFactorsTest {
  @Test
  public void factors() throws Exception {
    assertThat(factorsOf(1), is(empty()));
  }
}

讓它通過：

private List<Integer> factorsOf(int n) {
  return new ArrayList<>();
}

漸進加入測試#

接著對 2 做測試：

assertThat(factorsOf(2), contains(2));

private List<Integer> factorsOf(int n) {
  ArrayList<Integer> factors = new ArrayList<>();
  if (n > 1) factors.add(2);
  return factors;
}

對 3 的測試，靠一個小聰明（把 2 換成 n）通過：

private List<Integer> factorsOf(int n) {
  ArrayList<Integer> factors = new ArrayList<>();
  if (n > 1) factors.add(n);
  return factors;
}

4 帶來第一次重大跳躍#

factorsOf(4) 是第一次出現「結果含多個因數」：

private List<Integer> factorsOf(int n) {
  ArrayList<Integer> factors = new ArrayList<>();
  if (n > 1) {
    if (n % 2 == 0) {
      factors.add(2);
      n /= 2;
    }
  }
  if (n > 1) factors.add(n);
  return factors;
}

5、6、7 的測試自動通過。直到 8——出現了三個因數，必須把 if 改成 while：

private List<Integer> factorsOf(int n) {
  ArrayList<Integer> factors = new ArrayList<>();
  if (n > 1) {
    while (n % 2 == 0) {
      factors.add(2);
      n /= 2;
    }
  }
  if (n > 1) factors.add(n);
  return factors;
}

9 引出迴圈泛化#

要因數化 3，臨時加上「分別處理 3」的迴圈會帶來無止盡的重複；正解是把外層 if 也改成 while，並引入除數變數：

private List<Integer> factorsOf(int n) {
  ArrayList<Integer> factors = new ArrayList<>();
  int divisor = 2;
  while (n > 1) {
    while (n % divisor == 0) {
      factors.add(divisor);
      n /= divisor;
    }
    divisor++;
  }
  return factors;
}

最後重構成更精煉的雙層 for：

private List<Integer> factorsOf(int n) {
  ArrayList<Integer> factors = new ArrayList<>();
  for (int divisor = 2; n > 1; divisor++)
    for (; n % divisor == 0; n /= divisor)
      factors.add(divisor);
  return factors;
}

給定足夠的時間與空間，這個演算法可以分解任何整數。

Clojure 版本#

測試框架是 speclj ^↗，斷言關鍵字 should= 用於相等判斷。

同樣從退化測試開始#

(should= [] (prime-factors-of 1))

(defn prime-factors-of [n] [])

2 與 3 也照 Java 的節奏推進：

(should= [2] (prime-factors-of 2))

(defn prime-factors-of [n]
  (if (> n 1) [2] []))

(should= [3] (prime-factors-of 3))

(defn prime-factors-of [n]
  (if (> n 1) [n] []))

4 開始分歧#

從 factorsOf(4) 起，兩種風格的解法路徑就不同了。Clojure 直接走向遞迴：

(should= [2 2] (prime-factors-of 4))

(defn prime-factors-of [n]
  (if (> n 1)
    (if (zero? (rem n 2))
      (cons 2 (prime-factors-of (quot n 2)))
      [n])
    []))

關鍵點：

cons：把元素前置到串列前端
rem / quot：整數餘數與商
這個解法是真遞迴——尾呼叫位置上是 cons，不是 prime-factors-of 自己

在 Java 端此時還只是線性邏輯（兩個 if(n>1) 是預示但尚未真正迭代）；Clojure 端已經跳到了完整的非尾呼叫遞迴。

5、6、7、8 全部自動通過。

9 再度逼出泛化#

(should= [3 3] (prime-factors-of 9))

(defn prime-factors-of [n]
  (if (> n 1)
    (if (zero? (rem n 2))
      (cons 2 (prime-factors-of (quot n 2)))
      (if (zero? (rem n 3))
        (cons 3 (prime-factors-of (quot n 3)))
        [n]))
    []))

但這個寫法不可持續——5、7、11、13 都得照樣加。轉向迭代：

(defn prime-factors-of [n]
  (loop [n n
         divisor 2
         factors []]
    (if (> n 1)
      (if (zero? (rem n divisor))
        (recur (quot n divisor) divisor (conj factors divisor))
        (recur n (inc divisor) factors))
      factors)))

關鍵點：

loop：在原地建立一個匿名函式
recur：在 loop 區塊內重新呼叫該匿名函式，啟用 TCO
三個迴圈狀態變數（n、divisor、factors）各有各的初始值
cons 換成了 conj——factors 是 vector，conj 從末端附加（而非從前端）

「先用真遞迴解 4，再被 9 逼著轉迭代」這個 U-turn 給了一條經驗法則：有得選的話，優先用尾遞迴而非真遞迴。

結論#

從這一輪比較，可以歸納出幾點觀察：

測試序列幾乎一致：Java 與 Clojure 在 1 ～ 9 的測試節奏完全相同。測試是比語言更基礎的東西——它們比寫法更接近問題本質
解法策略卻提早分歧：在 Java 端尚未需要迴圈時（4 的測試），Clojure 已經非用遞迴不可。遞迴在語意上比 while 更基本
Clojure 走過一次 U-turn：當初為 4 選了真遞迴，被 9 的測試逼得改寫——若一開始就用尾遞迴會更順
最終演算法結構不同：Java 是雙層巢狀迴圈；Clojure 是兩個獨立的尾遞迴呼叫

哪個版本更好？以執行速度而言，Java 比 Clojure 快得多；除此之外，對於兩種語言都熟悉的人來說，兩者讀起來、結構上都不分軒輊。
然而，本章是這場比較中最不分勝負的一章。隨著題目變難，兩種風格的差異會越來越明顯。