在 JavaScript 中,遞歸函數的空間復雜度主要取決于兩個因素:遞歸調用棧的深度以及函數本身的參數。
以階乘函數為例,其遞歸實現如下:
function factorial(n) {
if (n === 0) return 1;
return n * factorial(n - 1);
}
在這個例子中,遞歸調用棧的深度為 n
(因為每次調用都會將 n
減 1,直到 n
為 0 時停止調用)。同時,函數本身接收一個參數 n
。因此,該遞歸函數的空間復雜度為 O(n)。
需要注意的是,雖然遞歸實現可以直觀地解決問題,但在某些情況下可能會導致棧溢出等問題。在實際編程中,可以考慮使用迭代實現來避免這些問題。例如,上述階乘函數的迭代實現如下:
function factorial(n) {
let result = 1;
for (let i = 1; i <= n; i++) {
result *= i;
}
return result;
}
這個迭代實現的空間復雜度為 O(1),因為只需要常數級別的額外空間來保存變量 result
和循環計數器 i
。