Javascript尾遞迴程式設計

語言: CN / TW / HK

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)); ```