一、什麼是 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)
執行過程：
factorial(5)->5 * factorial(4)factorial(4)->4 * factorial(3)factorial(3)->3 * factorial(2)factorial(2)->2 * factorial(1)factorial(1)->1 * factorial(0)factorial(0)->1（基底條件）- 回溯：
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)] -> 逐步彈出
過程：
countDown(3)推入，印 3，呼叫countDown(2)。countDown(2)推入，印 2，呼叫countDown(1)。countDown(1)推入，印 1，呼叫countDown(0)。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 迴圈
遞迴：程式碼簡潔，適合複雜分解問題。 佔用調用棧，效能較低。
迴圈：效能更高，記憶體使用少。 程式碼可能較冗長。
