Javascript尾遞歸編程
theme: channing-cyan highlight: androidstudio
尾遞歸編程思想
遞歸是編程中必不可少的一環,在算法和工程上會經常使用,但是隨着計算量的增大,函數堆棧會大量堆積上一函數上下文中的變量和方法,會導致主線程棧的空間不足而造成棧溢出錯誤,由於新的函數壓入堆棧後,上一函數仍然在堆棧中未被釋放,因此內存資源消耗會十分大,對性能也會有很大影響。
我們知道遞歸寫起來確實方便,邏輯也容易理解,最簡單的斐波那契數列問題,跳樓梯,一次只能1步或2步,跳n格有多少種方法
最容易的遞歸
js
// 限制條件 countOfStep>0
function jump(countOfStep) {
if (countOfStep <= 0) return 0;
function jumpRecursive(innerCountOfStep) {
if (innerCountOfStep < 0) return 0;
if (innerCountOfStep === 1 || innerCountOfStep === 0) return 1;
return jumpRecursive(innerCountOfStep - 1) + jumpRecursive(innerCountOfStep - 2);
}
return jumpRecursive(countOfStep);
}
很明顯上述遞歸沒有任何優化,利用函數堆棧來實現對上一結果的保存作為下一結果的支撐,函數開銷大。
運用緩存結果思想解決函數開銷
js
function jumpWithoutFuncCost(countOfStep) {
if(countOfStep<=0) return 0;
const saves = new Array(countOfStep + 1).fill(0);
[saves[0], saves[1]] = [1, 1];
for (let i = 2; i <= countOfStep; i++) {
saves[i] = saves[i - 1] + saves[i - 2];
}
return saves[countOfStep];
}
是解決了數據過大棧溢出問題了,不過也同時帶來空間開銷
迭代方法
js
function jumpIteritive(countOfStep) {
if(countOfStep<=0) return 0;
let [prefix, suffix] = [1, 1];
for (let i = 2; i <= countOfStep; i++) {
let temp = suffix;
suffix += prefix;
prefix = temp;
}
return suffix;
}
如果是複雜點的問題迭代法是比較難想出來的。但凡可以實現迭代處理的方法可以用尾遞歸實現,遞歸的實現更具有可讀性和簡潔性。
尾遞歸實現
js
function jumpTailRecursive(countOfStep, prev = 1, next = 1) {
if(countOfStep<=0) return 0;
if (countOfStep === 1) return next;
return jumpTailRecursive(--countOfStep, next, prev + next);
}
原理圖解
關於Javascript沒有實現尾遞歸優化
Javascript由於某些原因,JavaScript引擎實現者認為特性不合理,以及各大廠商的權力糾紛問題,TC39提案仍未落實尾遞歸優化方案。
如果要實現JavaScript尾遞歸優化,需要採用蹦牀函數輔助實現,才能實現和迭代一樣避免棧溢出情況。
trampoline實現
```js function jumpTailRecursiveTrampolined(countOfStep, prev = 1, next = 1) { if (countOfStep <= 0) return 0; if (countOfStep === 1) return next; return () => jumpTailRecursiveTrampolined(--countOfStep, next, prev + next); }
function trampoline(F){ return function(...args){ F = F.bind(this, ...args); while (F instanceof Function) { F = F(); } return F; } }
const uniformLog = (element) => console.log(JSON.stringify(element, undefined, 4)); uniformLog(trampoline(jumpTailRecursiveTrampolined)(3)); ```