JavaScript 遞歸性能優化

遞歸是編程中強大的技術，但在 JavaScript 中如果不注意優化可能會導致性能問題甚至棧溢出。以下是幾種優化遞歸性能的方法：

1. 尾調用優化 (Tail Call Optimization, TCO)

ES6 引入了尾調用優化，但只在嚴格模式下有效：

'use strict';// 普通遞歸
function factorial(n) {if (n === 1) return 1;return n * factorial(n - 1); // 不是尾調用
}// 尾遞歸優化版本
function factorial(n, total = 1) {if (n === 1) return total;return factorial(n - 1, n * total); // 尾調用
}

注意：目前主流瀏覽器引擎對 TCO 的支持有限，Node.js 中需要開啟特定 flag。

2. 使用循環替代遞歸

// 遞歸版
function fibonacci(n) {if (n <= 1) return n;return fibonacci(n - 1) + fibonacci(n - 2);
}// 循環版（性能更好）
function fibonacci(n) {let a = 0, b = 1, temp;for (let i = 0; i < n; i++) {temp = a;a = b;b = temp + b;}return a;
}

3. 記憶化 (Memoization)

緩存已計算的結果避免重復計算：

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

4. 使用 trampoline 技術

將遞歸轉換為循環執行：

function trampoline(fn) {return function(...args) {let result = fn(...args);while (typeof result === 'function') {result = result();}return result;};
}// 使用
const factorial = trampoline(function myself(n, acc = 1) {if (n <= 1) return acc;return () => myself(n - 1, n * acc);
});

5. 限制遞歸深度

function limitedRecursion(fn, maxDepth = 1000) {return function(...args) {if (--maxDepth < 0) throw new Error('Maximum call stack exceeded');return fn(...args);};
}

6. 使用異步遞歸

將遞歸調用拆分為多個事件循環：

function asyncRecursion(n, callback) {if (n <= 0) return process.nextTick(() => callback(1));process.nextTick(() => {asyncRecursion(n - 1, (result) => {callback(n * result);});});
}

最佳實踐建議

1. 優先考慮尾遞歸形式
2. 對于深度遞歸考慮使用循環
3. 對于重復計算使用記憶化
4. 對于非常深的遞歸考慮 trampoline 或異步方式
5. 始終設置遞歸終止條件

記住，遞歸雖然優雅，但在 JavaScript 中并不總是最高效的解決方案。根據具體場景選擇最適合的方法。