JS學習筆記#23 | 遞迴（Recursion）

undefined on Tenor

一、什麼是 Recursion？

遞迴是指一個函數自己呼叫自己，用來解決可以分解成相似小問題的大問題。它就像一層層深入，最後再一層層回來的過程。

二、遞迴的兩個核心要素

1.基底條件（Base Case）

2.遞迴步驟（Recursive Case）

函數自我調用，每次縮減問題規模，直到觸及基底條件。

3.範例：階乘

function factorial(n) {
    if (n === 0) { // 基底條件
        return 1;
    }
    return n * factorial(n - 1); // 遞迴步驟
}

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

執行過程：

1. factorial(5) -> 5 * factorial(4)
2. factorial(4) -> 4 * factorial(3)
3. factorial(3) -> 3 * factorial(2)
4. factorial(2) -> 2 * factorial(1)
5. factorial(1) -> 1 * factorial(0)
6. factorial(0) -> 1（基底條件）
7. 回溯：1 * 1 * 2 * 3 * 4 * 5 = 120

視覺化：

深入：5 -> 4 -> 3 -> 2 -> 1 -> 0

返回：1 -> 1 -> 2 -> 6 -> 24 -> 120

三、遞迴與調用棧（Call Stack）

遞迴依賴調用棧來記錄每層調用：

• 每次自我調用，函數推入調用棧。
• 達到基底條件後，棧開始彈出，計算結果。

function countDown(n) {
    if (n <= 0) {
        console.log("Done");
        return;
    }
    console.log(n);
    countDown(n - 1);
}

countDown(3);
// 輸出：
// 3
// 2
// 1
// Done

調用棧變化：

[] -> [countDown(3)] -> [countDown(3), countDown(2)] -> [countDown(3), countDown(2), countDown(1)] -> [countDown(3), countDown(2), countDown(1), countDown(0)] -> 逐步彈出

過程：

1. countDown(3) 推入，印 3，呼叫 countDown(2)。
2. countDown(2) 推入，印 2，呼叫 countDown(1)。
3. countDown(1) 推入，印 1，呼叫 countDown(0)。
4. countDown(0) 推入，印 "Done"，返回，棧彈出。

四、遞迴的實際應用

1.數學問題：階乘、斐波那契數列。

// 斐波那契範例
function fibonacci(n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}
console.log(fibonacci(6)); // 8 (0, 1, 1, 2, 3, 5, 8)

2.資料結構遍歷：樹或巢狀陣列

function flattenArray(arr) {
    let result = [];
    arr.forEach(item => {
        if (Array.isArray(item)) {
            result = result.concat(flattenArray(item));
        } else {
            result.push(item);
        }
    });
    return result;
}
console.log(flattenArray([1, [2, 3], [4, [5]]])); // [1, 2, 3, 4, 5]

3.分治演算法：快速排序、合併排序。

五、遞迴的注意事項

1.棧溢出（Stack Overflow）：

調用棧有大小限制（通常幾千層）。

如果遞迴太深或無基底條件，會溢出。

function infinite(n) {
    return infinite(n + 1);
}
infinite(1); // 報錯：Maximum call stack size exceeded

2.效能問題：

遞迴每次調用都推入調用棧，佔用記憶體。

對於簡單問題，迴圈可能更高效。

function factorialLoop(n) {
    let result = 1;
    for (let i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

遞迴 vs 迴圈

遞迴：程式碼簡潔，適合複雜分解問題。 佔用調用棧，效能較低。

迴圈：效能更高，記憶體使用少。 程式碼可能較冗長。