JavaScript 課程 – 函式（Functions）

主題：遞迴（Recursion）

簡介

在程式設計中，遞迴是一種讓函式自行呼叫自身的技巧。看似簡單卻能解決許多「分而治之」的問題，例如樹狀結構的遍歷、排列組合的產生，以及各種數學演算法（如階乘、費波那契數列）。
對於 JavaScript 開發者而言，掌握遞迴不僅能寫出更具表達力的程式碼，也能在面試或實務專案中展現演算法思維。尤其在處理 JSON、DOM 或 React 組件樹時，遞迴往往是最直觀且效能可接受的解法。

本篇文章將從 遞迴的基本概念、實作範例、常見陷阱，到 最佳實踐與實務應用，一步步帶你深入了解遞迴在 JavaScript 中的運用，適合 初學者到中階開發者閱讀。

核心概念

1. 什麼是遞迴？

遞迴（Recursion）指的是函式在執行過程中直接或間接呼叫自己。遞迴的運作模式通常包含兩個關鍵要素：

基礎情況（Base Case）：結束遞迴的條件，避免無限呼叫。
遞迴步驟（Recursive Step）：把原問題拆解成較小的子問題，然後呼叫自身解決子問題。

例子：計算 n 的階乘 n! = n × (n-1) × … × 1。

基礎情況：0! = 1。

遞迴步驟：n! = n × (n-1)!。

只要每次呼叫都能讓問題規模 嚴格縮小，最終必會達到基礎情況，遞迴就會安全結束。

2. 為什麼要使用遞迴？

場景	使用遞迴的好處
樹狀資料（如 DOM、JSON）	代碼簡潔，與資料結構的自然遞迴形態相呼應
組合問題（排列、子集合）	直接映射「選或不選」的決策樹
分治演算法（快速排序、合併排序）	把大問題拆成子問題，遞迴自然實現 divide & conquer
狀態機（有限自動機、遊戲樹）	以遞迴方式探索所有可能的狀態

雖然迴圈（for、while）也能解決許多相同問題，但遞迴往往能讓 程式碼更具可讀性，尤其在處理「層層嵌套」的資料時。

3. 遞迴 vs 迴圈

比較項目	遞迴	迴圈
表達力	直接映射問題的遞迴結構	需要額外的索引或堆疊管理
記憶體	每次呼叫會產生一個新的執行上下文（stack frame），可能導致 stack overflow	只使用單一執行上下文，記憶體需求較低
尾端遞迴（Tail Call）	若瀏覽器支援 ES6 的 Tail Call Optimization (TCO)，可與迴圈媲美	本身就是迴圈結構

在 JavaScript 中，大多數瀏覽器尚未完整支援 TCO，因此在遞迴深度可能很大的情況下，需要自行考慮改寫為迴圈或使用顯式堆疊。

4. 基礎範例

4.1 階乘（Factorial）

/**
 * 計算正整數 n 的階乘
 * @param {number} n - 必須是非負整數
 * @returns {number} n!
 */
function factorial(n) {
  // 基礎情況：0! = 1
  if (n === 0) return 1;
  // 遞迴步驟：n! = n * (n-1)!
  return n * factorial(n - 1);
}

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

說明：每一次呼叫 factorial 都把 n 減 1，最終會抵達 0，此時返回 1 結束遞迴。

4.2 費波那契數列（Fibonacci）

/**
 * 計算第 n 個費波那契數（從 0 開始）
 * @param {number} n
 * @returns {number}
 */
function fibonacci(n) {
  // 基礎情況：第 0、1 個數分別是 0、1
  if (n === 0) return 0;
  if (n === 1) return 1;
  // 遞迴步驟：F(n) = F(n-1) + F(n-2)
  return fibonacci(n - 1) + fibonacci(n - 2);
}

// 測試
console.log(fibonacci(7)); // 13

提示：此實作簡潔但會產生大量重複計算，實務上會改用 記憶化（memoization） 或迭代方式提升效能。

4.3 樹狀結構遍歷（Depth‑First Search）

/**
 * 以深度優先方式遍歷樹狀物件，並收集所有節點的 name
 * @param {Object} node - 節點物件，必須有 children 陣列
 * @param {Array} result - 用來累積結果的陣列（外部傳入）
 */
function dfs(node, result = []) {
  // 先處理當前節點
  result.push(node.name);

  // 若有子節點，遞迴處理每一個
  if (Array.isArray(node.children)) {
    node.children.forEach(child => dfs(child, result));
  }

  return result;
}

// 範例樹
const tree = {
  name: 'A',
  children: [
    { name: 'B', children: [{ name: 'D' }, { name: 'E' }] },
    { name: 'C', children: [{ name: 'F' }] }
  ]
};

console.log(dfs(tree)); // ['A', 'B', 'D', 'E', 'C', 'F']

說明：遞迴自然對應樹的層次結構，程式碼比手寫堆疊更直觀。

4.4 子集合（Power Set）產生

/**
 * 產生給定陣列的所有子集合（Power Set）
 * @param {Array} arr
 * @returns {Array<Array>}
 */
function powerSet(arr) {
  // 基礎情況：空集合只有一個子集合——空集合本身
  if (arr.length === 0) return [[]];

  // 取出最後一個元素，遞迴產生其餘元素的子集合
  const last = arr[arr.length - 1];
  const withoutLast = powerSet(arr.slice(0, -1));

  // 把 last 加入每個子集合，形成新子集合
  const withLast = withoutLast.map(set => [...set, last]);

  // 合併兩者
  return [...withoutLast, ...withLast];
}

// 測試
console.log(powerSet([1, 2, 3]));
/* [
  [],        [1],
  [2],       [1,2],
  [3],       [1,3],
  [2,3],     [1,2,3]
] */

概念：每一步把「包含最後一個元素」與「不包含」兩種情況合併，遞迴層數等於陣列長度。

4.5 尾端遞迴（Tail Recursion）示範

/**
 * 使用尾端遞迴計算階乘（若環境支援 TCO，會避免 stack overflow）
 * @param {number} n
 * @param {number} acc - 累積乘積，預設為 1
 * @returns {number}
 */
function factorialTail(n, acc = 1) {
  if (n === 0) return acc;          // 基礎情況
  return factorialTail(n - 1, n * acc); // 最後一步直接回傳遞迴呼叫
}

// 測試
console.log(factorialTail(6)); // 720

備註：即使目前大多數瀏覽器不會真正做 TCO，寫成尾端遞迴仍有助於未來可移植性與可讀性。

常見陷阱與最佳實踐

1. 忘記基礎情況

最常見的錯誤是遞迴函式缺少或寫錯基礎情況，導致 無限遞迴，最終拋出 RangeError: Maximum call stack size exceeded。
做法：在寫遞迴前，先用紙筆列出「什麼時候應該停止」的條件。

2. 遞迴深度過大

JavaScript 的執行堆疊大小有限（大約 10,000~30,000 層，依瀏覽器而異）。對於可能產生深層遞迴的問題（如遍歷深度超過千層的樹），建議改寫為 迭代 + 明確堆疊 的方式。

function iterativeDFS(root) {
  const stack = [root];
  const result = [];

  while (stack.length) {
    const node = stack.pop();
    result.push(node.name);
    if (node.children) {
      // 先放子節點，讓左子樹先被處理
      for (let i = node.children.length - 1; i >= 0; i--) {
        stack.push(node.children[i]);
      }
    }
  }
  return result;
}

3. 重複計算

如前面的費波那契範例，純遞迴會產生指數級的呼叫次數。解法：

記憶化（Memoization）：把已計算過的結果快取起來。
動態規劃（DP）：改寫為迭代方式。

const memoFib = (function () {
  const cache = {};
  return function fib(n) {
    if (n in cache) return cache[n];
    if (n <= 1) return n;
    return (cache[n] = fib(n - 1) + fib(n - 2));
  };
})();

4. 副作用（Side Effects）

遞迴函式如果在每層都改變全域變數或傳入的參數，容易產生難以追蹤的錯誤。建議：

儘量使用 純函式（pure function），即不改變外部狀態。
若需要累積結果，將結果作為參數傳入（如 dfs(node, result)），或在返回值中組合。

5. 使用 `arguments.callee`（已被棄用）

在 ES5 以前，開發者常用 arguments.callee 取得當前函式的引用，實作遞迴。但在嚴格模式（"use strict"）以及 ES6+ 中已被禁止。改用具名函式或 箭頭函式（需自行命名）：

const sum = function recur(n) {
  if (n <= 0) return 0;
  return n + recur(n - 1);
};

6. 尾端遞迴的可行性

雖然 ES6 標準規範了尾端呼叫優化（Tail Call Optimization），但目前只有少數引擎（如 Safari）完整支援。實務上，仍應將遞迴深度控制在安全範圍內，或改寫為迴圈。

實際應用場景

場景	為什麼適合遞迴	範例簡述
DOM 樹遍歷	樹狀結構天然遞迴	`querySelectorAll` 替代方案：自訂深度搜尋
JSON 深層比對	需要逐層比對子屬性	比較兩筆資料是否結構相同
演算法教學（排序、搜尋）	分治法需要把問題切割	快速排序、合併排序的實作
組合生成（密碼、測試資料）	每一層選擇「取/不取」	產生所有可能的字元排列
AI 樹搜索（迷宮、遊戲）	探索所有可能的走法	深度優先搜尋 (DFS) 迷宮路徑
遞迴式 UI（React）	元件樹的遞迴渲染	渲染多層目錄結構的側邊欄

實務小技巧：在 React 中，若要渲染遞迴樹形結構，請務必為每個子元件提供 唯一的 key，避免不必要的重新渲染。

總結

遞迴是 將問題拆解成相同形式子問題 的強大工具，特別適合處理 樹狀結構、組合問題與分治演算法。掌握以下要點，就能在 JavaScript 中安全且高效地使用遞迴：

明確基礎情況：永遠先寫出何時停止遞迴。
確保問題規模遞減：每一次遞迴呼叫都必須讓問題變「更小」。
警惕堆疊深度：對於可能超過數千層的情況，考慮改寫為迭代或使用顯式堆疊。
避免重複計算：使用記憶化或改寫為迭代式 DP。
保持純函式：減少副作用，提升可讀性與可測試性。
了解環境限制：目前瀏覽器對尾端遞迴的支援有限，實務上仍以迴圈為安全保證。

透過本文的 概念說明、多樣範例、以及 最佳實踐，你應該已經能夠自行設計與除錯遞迴函式，並將它們應用於日常開發與演算法挑戰中。祝你在 JavaScript 的遞迴之路上 寫出更簡潔、更強大的程式碼！ 🚀