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
C++

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)
    }
}

#include <iostream>

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);
    }
};

int main() {
    std::cout << Solution::factorial(5) << std::endl; // 輸出: 120 (5 * 4 * 3 * 2 * 1)
}

C++ 的整數溢位

Python 的整數沒有固定寬度，不會溢位；但 C++ 跟 Java 一樣，int 通常只有 32 位元。階乘成長得非常快，n * factorial(n - 1) 這個乘法只要 n 大於 12 左右，結果就會超過 int 能表示的範圍（約 ±21 億），導致溢位算出錯誤答案。範例中 n = 5 還不會踩到這個問題，但如果題目的 n 可能比較大，記得把回傳型別與運算都改成 long long。

遞迴到底怎麼跑的？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，就是以這個術語來命名的（雖然已經是老梗了，但還是要講一下）。

C++ 與 Java、Python 在 Stack 大小上的差異

C++ 預設的呼叫堆疊大小有限（依平台/編譯器通常是 1MB～8MB），跟 Java 類似，一旦遞迴太深就會真的把程式搞當掉（crash），而不是丟出一個容易理解的錯誤訊息。

比較特別的是 Python，它預設的遞迴深度限制大約只有 1000 層，遞迴還沒逼近 Call Stack 實際容量上限前，就會先丟出 RecursionError，某種程度上反而比 C++/Java 更早示警，代價是有時候「其實記憶體還夠用」的深遞迴也會被提早擋下來，需要手動呼叫 sys.setrecursionlimit() 才能放寬限制。

遞迴 vs 迴圈（Iteration）

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

Python
JavaScript
Java
C++

# 用迴圈計算階乘
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;
    }
}

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）​

適用情況​

常見誤區​

延伸閱讀​