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

「其他文章」