Recursion

遞迴（Recursion）是一種程式設計技巧、思考邏輯或是演算法策略。

它指的是在函式中呼叫自己的行為，用來將大問題拆解成相似的小問題，本身不算是一個「完整的演算法」。

當面對重複性問題時，常常可用迴圈（Loop）來處理，而 Recursion 則是另一種方式，甚至在某些情況下，使用 Recursion 會更方便。

白話理解

想像俄羅斯套娃，打開最外層的娃娃，裡面是一個一模一樣、只是尺寸更小的娃娃，一路打開下去，直到打開最小的那一個（不能再打開為止）。

遞迴呼叫自己就是這種感覺：每一層都在處理「同樣的問題」，只是規模變小了一點，直到縮小到可以直接給出答案的程度。

新手小提醒

遞迴是很多人學 DSA 的第一個卡關點，覺得「函式怎麼可以呼叫自己」很難想像。

不用急著一次看懂全部，先記住一句話：「相信自己算出答案」。也就是先假設「呼叫自己」這件事已經能正確算出小問題的答案，你只需要專心處理「當前這一步」要做什麼就好，不用在腦中同時模擬所有層級發生的事。

必要條件

使用遞迴，有兩個必要條件：

Base Case：讓遞迴停止的情形
輸入不同的 input

如果沒有 Base Case，或是每次呼叫自己時 input 都沒有往 Base Case 靠近，遞迴就會無窮無盡地呼叫下去，直到程式當機，這種情況稱為 Stack Overflow（後面會解釋原因）。

範例：計算階乘

階乘（例如 5! = 5 × 4 × 3 × 2 × 1）是理解遞迴最直覺的例子。

Python
JavaScript
Java

def factorial(n):
    # 1. Base Case：當 n 降到 1 或 0 時，停止呼叫並回傳 1
    if n == 0 or n == 1:
        return 1

    # 2. 遞迴步驟：n! = n * (n-1)!
    return n * factorial(n - 1)

print(factorial(5))  # 輸出: 120 (5 * 4 * 3 * 2 * 1)

function factorial(n) {
  // 1. Base Case：當 n 降到 1 或 0 時，停止呼叫並回傳 1
  if (n === 0 || n === 1) {
    return 1;
  }

  // 2. 遞迴步驟：n! = n * (n-1)!
  return n * factorial(n - 1);
}

console.log(factorial(5)); // 輸出: 120 (5 * 4 * 3 * 2 * 1)

class Solution {
    public static int factorial(int n) {
        // 1. Base Case：當 n 降到 1 或 0 時，停止呼叫並回傳 1
        if (n == 0 || n == 1) {
            return 1;
        }

        // 2. 遞迴步驟：n! = n * (n-1)!
        return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        System.out.println(factorial(5)); // 輸出: 120 (5 * 4 * 3 * 2 * 1)
    }
}

遞迴到底怎麼跑的？Call Stack 逐步拆解

新手最卡的地方，是不知道電腦執行到 return n * factorial(n - 1) 這一行時，到底發生了什麼事。

其實電腦會利用一個叫做 Call Stack 的結構（可參考 Stack），把「還沒算完、正在等待答案」的呼叫一層一層疊起來。

以 factorial(3) 為例，可以拆成兩個階段：

階段一：往下「疊」（每次呼叫自己，都先暫停等答案）

factorial(3)                       // 還不知道答案，要先等 factorial(2)
  → factorial(2)                   // 還不知道答案，要先等 factorial(1)
    → factorial(1)                 // 符合 Base Case，直接回傳 1

呼叫的當下，factorial(3) 那一行程式碼會卡在 n * factorial(n - 1) 這一步，記住「我是 n=3，我在等下一層的答案」，然後把控制權交給 factorial(2)。factorial(2) 也是同樣的道理，繼續往下疊，直到遇到 Base Case 為止。

階段二：往上「收」（Base Case 算出答案後，一層一層往回傳）

factorial(1) 回傳 1
  → factorial(2) = 2 * 1 = 2   回傳 2
    → factorial(3) = 3 * 2 = 6   回傳 6

一旦有了確定的答案（Base Case），前面暫停的每一層就可以依序把自己欠的乘法算完，並把結果丟給上一層，直到回到最一開始呼叫的地方。

資訊

為什麼會 Stack Overflow？
Call Stack 的空間是有限的。如果遞迴一直沒有遇到 Base Case（例如忘記寫 Base Case，或是 input 沒有往 Base Case 靠近），呼叫就會無止盡地往下疊，疊到超過 Call Stack 的容量上限，就會產生 "Maximum call stack size exceeded" 這類錯誤，也就是 Stack Overflow。

全球知名的程式技術問答網站 Stack Overflow，就是以這個術語來命名的（雖然已經是老梗了，但還是要講一下）。

遞迴 vs 迴圈（Iteration）

同樣的問題，通常都能用遞迴或迴圈寫出來，兩者是可以互相轉換的。

Python
JavaScript
Java

# 用迴圈計算階乘
def factorial_loop(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

// 用迴圈計算階乘
function factorialLoop(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

class Solution {
    // 用迴圈計算階乘
    public static int factorialLoop(int n) {
        int result = 1;
        for (int i = 2; i <= n; i++) {
            result *= i;
        }
        return result;
    }
}

比較項目	Recursion	Iteration（迴圈）
程式碼可讀性	面對「樹狀」或「可以拆成同樣小問題」的情境時，通常更簡潔直覺	面對單純重複的操作時，通常更直接好懂
空間消耗	額外消耗 Call Stack 空間，通常是 O(n)	通常只需要 O(1) 的額外空間
執行效能	每次呼叫函式都有額外的開銷（overhead）	沒有函式呼叫的開銷，速度通常較快
適合情境	Tree、Graph 等本身就有「遞迴結構」的資料，或是 Backtracking、Divide and Conquer 類型的問題	單純的計數、加總等線性重複的操作

提示

並不是遞迴比較「高級」，兩者只是解決問題的不同工具。
如果一個問題用迴圈就能簡單解決，通常不需要特地改寫成遞迴；但如果問題本身帶有「一層包一層」的結構（例如 Tree Traversal、階乘、費氏數列），用遞迴來寫反而會更貼近問題本質，程式碼也更好懂。

適用情況

具有「一層包一層」天生遞迴結構的資料：例如 Tree、Graph 的走訪，本身就是「處理完自己，再交給子節點處理」的結構。
可以拆成同樣小問題的問題：例如階乘、費氏數列、Divide and Conquer 類型的問題，子問題和原問題長得一模一樣，只是規模變小。
需要「試錯後退回上一步」的窮舉問題：例如 Backtracking，在遞迴的基礎上多了撤銷選擇的概念。
需要解析巢狀結構：例如巢狀的 JSON、檔案系統目錄，天生就是遞迴的階層結構，適合用遞迴逐層拆解。

常見誤區

忘記寫 Base Case，或是 Base Case 寫錯：這是最常導致 Stack Overflow 或錯誤答案的原因，寫遞迴時，建議第一步永遠先想「什麼時候該停下來」。
每次呼叫自己時，input 沒有往 Base Case 靠近：例如把 factorial(n - 1) 誤寫成 factorial(n)，會造成無窮遞迴。
誤以為遞迴一定比較慢或比較快：實際效能取決於問題本身與寫法（例如有沒有重複計算，可參考 Dynamic Programming 如何用「記憶」來優化遞迴）。
想一次在腦中模擬完所有層級：不需要這樣做，只要確認「Base Case 正確」以及「目前這一層在拿到子問題答案後，知道該怎麼處理」，遞迴就會自動正確運作。

必要條件​

範例：計算階乘​

遞迴到底怎麼跑的？Call Stack 逐步拆解​

階段一：往下「疊」（每次呼叫自己，都先暫停等答案）​

階段二：往上「收」（Base Case 算出答案後，一層一層往回傳）​

遞迴 vs 迴圈（Iteration）​

適用情況​

常見誤區​

延伸閱讀​