遞迴一定要有「出口」：認識 FP 中的基本條件（Base Case)

在函數式程式設計（Functional Programming，簡稱 FP）中，有一條非常重要的規則： 所有的遞迴呼叫，最後都必須收斂到某種「不再需要遞迴」的情況。 這個情況就叫做 基本條件（Base Case），也有人稱它為「終止條件」。

這篇文章會用淺白的文字和 JavaScript 範例，帶你一步一步理解這個觀念。

一、什麼是遞迴？

遞迴（Recursion）就是「函式自己呼叫自己」。

聽起來有點抽象？想像一個生活情境：

你在排隊，想知道自己排第幾個。你問前面的人：「你排第幾個？」前面的人也不知道，於是他也問他前面的人…… 一直問到 排在最前面的人，他說：「我是第 1 個！」接著答案一路往回傳：第 2 個、第 3 個……最後你就知道自己排第幾了。

這裡的關鍵是：「排在最前面的人」不需要再問別人，他可以直接給出答案。這就是所謂的「基本條件」。

二、什麼是基本條件（Base Case）？

基本條件就是遞迴的「出口」，它有兩個特徵：

不會再呼叫自己：走到這一步，函式可以直接回傳答案。
每次遞迴都要更接近它：問題必須一次比一次「小」，最後才會走到出口。

如果沒有基本條件，或是永遠走不到基本條件，函式就會無限呼叫自己，最後程式當掉，出現這個經典錯誤：

RangeError: Maximum call stack size exceeded

意思是「呼叫堆疊爆掉了」，也就是俗稱的 爆 stack。

三、第一個範例：倒數計時

❌ 錯誤示範：沒有基本條件

function countdown(n) {
  console.log(n);
  countdown(n - 1); // 一直呼叫自己，永遠停不下來！
}

countdown(3);
// 3, 2, 1, 0, -1, -2, ...... 直到程式爆掉

這個函式沒有出口，會一路數到負無限大（其實是先爆 stack）。

✅ 正確示範：加上基本條件

function countdown(n) {
  // 基本條件：數到 0 就停止，不再呼叫自己
  if (n <= 0) {
    console.log("結束！");
    return;
  }

  console.log(n);
  countdown(n - 1); // 遞迴呼叫：n 每次都變小，越來越接近 0
}

countdown(3);
// 3
// 2
// 1
// 結束！

注意兩個重點：

if (n <= 0) 就是基本條件，走到這裡直接 return，不再遞迴。
每次呼叫都傳入 n - 1，問題越變越小，保證最後一定會碰到基本條件。

四、第二個範例：階乘（Factorial)

階乘是遞迴的經典範例。5! 的意思是 5 × 4 × 3 × 2 × 1 = 120。

用數學的方式拆解：

5! = 5 × 4!
4! = 4 × 3!
3! = 3 × 2!
2! = 2 × 1!
1! = 1        ← 這裡就是基本條件！不用再拆了

寫成 JavaScript：

function factorial(n) {
  // 基本條件：1 的階乘就是 1，直接回傳，不再遞迴
  if (n <= 1) {
    return 1;
  }

  // 遞迴呼叫：把問題變小（n 變成 n - 1）
  return n * factorial(n - 1);
}

console.log(factorial(5)); // 120

執行過程長什麼樣子？

factorial(5)
= 5 * factorial(4)
= 5 * (4 * factorial(3))
= 5 * (4 * (3 * factorial(2)))
= 5 * (4 * (3 * (2 * factorial(1))))
= 5 * (4 * (3 * (2 * 1)))   ← 碰到基本條件，開始往回算
= 5 * (4 * (3 * 2))
= 5 * (4 * 6)
= 5 * 24
= 120

可以看到，整個遞迴像「下樓梯」一樣一路往下， 碰到基本條件（factorial(1) 回傳 1）之後，才開始一路往回收斂出答案。

五、第三個範例：加總陣列（FP 風格）

在 FP 中，我們常用遞迴取代 for 迴圈來處理陣列。處理陣列時，最常見的基本條件是：空陣列。

function sum(arr) {
  // 基本條件：空陣列的總和就是 0
  if (arr.length === 0) {
    return 0;
  }

  // 拆解：第一個元素 + 剩下元素的總和
  const [first, ...rest] = arr;
  return first + sum(rest); // 每次遞迴，陣列都變短，最後一定會變成空陣列
}

console.log(sum([1, 2, 3, 4])); // 10

執行過程：

sum([1, 2, 3, 4])
= 1 + sum([2, 3, 4])
= 1 + (2 + sum([3, 4]))
= 1 + (2 + (3 + sum([4])))
= 1 + (2 + (3 + (4 + sum([]))))
= 1 + (2 + (3 + (4 + 0)))   ← 空陣列碰到基本條件，回傳 0
= 10

這正是 FP 的核心思考方式：

把大問題拆成「一小步 + 更小的同樣問題」，直到問題小到可以直接回答為止。

六、為什麼 FP 特別強調基本條件？

在 FP 的世界裡，我們盡量不使用 for、while 這類會改變變數的迴圈，而是用遞迴來表達「重複」這件事。

既然遞迴取代了迴圈，那麼：

迴圈的世界	遞迴的世界
迴圈的「結束條件」（例如 `i < 10`）	遞迴的「基本條件」（Base Case）
每圈更新變數（`i++`）	每次遞迴傳入更小的問題（`n - 1`、`rest`）

沒有結束條件的迴圈會變成無窮迴圈；同樣地，沒有基本條件的遞迴就會無限呼叫自己。

所以 FP 才會有這條鐵律：

所有遞迴呼叫，都必須收斂到某個不涉及遞迴的情況（基本條件）。

七、寫遞迴的三步驟檢查清單

以後自己寫遞迴時，可以照這個順序思考：

先寫基本條件：什麼情況下答案「小到可以直接回答」？
- 數字問題 → 通常是 0 或 1
- 陣列問題 → 通常是空陣列 []
- 字串問題 → 通常是空字串 ""
再寫遞迴呼叫：怎麼把問題「變小一點」再丟給自己？
最後確認會收斂：每次遞迴後，問題是不是真的更接近基本條件？

只要這三點都做到，你的遞迴就一定會停下來，並算出正確答案。

八、小結

遞迴 = 函式自己呼叫自己。
基本條件（Base Case）= 遞迴的出口，是一個「不再需要遞迴」就能直接回答的情況。
每次遞迴都必須讓問題變得更小、更接近基本條件。
沒有基本條件的遞迴會無限執行，最後爆 stack。
在 FP 中，遞迴取代了迴圈，所以基本條件就像迴圈的結束條件一樣重要。

記住這句話就對了：

先想好怎麼「停」，再想怎麼「跑」。

一、什麼是遞迴？​

二、什麼是基本條件（Base Case）？​

三、第一個範例：倒數計時​

❌ 錯誤示範：沒有基本條件​

✅ 正確示範：加上基本條件​

四、第二個範例：階乘（Factorial)​

執行過程長什麼樣子？​

五、第三個範例：加總陣列（FP 風格）​

六、為什麼 FP 特別強調基本條件？​

七、寫遞迴的三步驟檢查清單​

八、小結​