/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
let n1 = 1;
let n2 = 2;
let sum = 0;
if (n === 1) return 1;
if (n === 2) return 2;
for (let i = 3; i <= n; i++) {
sum = n1 + n2;
n1 = n2;
n2 = sum;
}
return sum
};
异步任务进行的尾递归优化
async function trampoline(f) {
while (f && f instanceof Promise) {
await f.then(res => {
if (res && res instanceof Function) f = res()
else f = res
})
}
console.log(f)
}
function p () {
return new Promise((resolve, reject) => {
resolve(1)
})
}
作者: holyzheng 转载请注明出处
尾调优化
在知道尾递归之前,我们要知道什么是尾调用优化,因为尾调用优化是尾递归的基础。尾调用就是:在函数的最后一步调用另一个函数
尾调用优化的原理是什么?
按照阮一峰老师在es6的函数扩展中的解释就是:函数调用会在内存形成一个“调用记录”,又称“调用帧”(call frame),保存调用位置和内部变量等信息。如果在函数
A
的内部调用函数B
,那么在A
的调用帧上方,还会形成一个B
的调用帧。等到B
运行结束,将结果返回到A
,B
的调用帧才会消失。如果函数B
内部还调用函数C
,那就还有一个C
的调用帧,以此类推。所有的调用帧,就形成一个“调用栈”(call stack)。这里的“调用帧”和“调用栈”,说的应该就是“执行环境”和“调用栈”。因为尾调用时函数的最后一部操作,所以不再需要保留外层的调用帧,而是直接取代外层的调用帧,所以可以起到一个优化的作用。
尾递归优化
我们知道,递归虽然使用起来方便,但是递归是在函数内部调用自身,当递归次数达到一定数量级的时候,他形成的调用栈的深度是很可怕的,很可能会发生“栈溢出”错误。尾递归优化,就是利用尾调用优化的原理,对递归进行优化。举一个很常见的例子:
此函数没有进行任何的优化,当我们在控制台去执行此函数的时候,fibonacci(40)就已经出现了明显的响应慢的问题,fibonacci(50)的时候浏览器卡死。
此优化有两个点:首先进行了算法上的优化,减少了很多重复的计算,时间复杂度大大降低;第二进行了尾递归优化,按理说不会发生“栈溢出”。我们可以到控制台中再尝试,发现速度的提升不是一般的快,证明第一个优化生效了,但是当我们允许fibonacci(10000)的时候,报错了:
Uncaught RangeError: Maximum call stack size exceeded
,这就说明我们的尾递归优化并没有生效。为什么呢?局限性
上面说到,我们直接再浏览器的控制台中执行fibonacci(10000)的时候,发生了栈溢出,这是为什么呢?关于这一点,我目前查阅资料之后的理解就是,虽然es6已经提出了要实现尾递归优化,但是真正落地实现了尾递归优化的浏览器并不多。所以当我们使用尾递归进行优化的时候,依旧发生了“栈溢出”的错误。
蹦床函数
那怎么办呢?我们还有另一个方法去达到尾递归优化的效果,那就是使用
蹦床函数(trampoline)
。代码修改为返回一个新函数。
两个函数结合就可以将递归状态为循环,栈溢出的问题也就解决了。
动态规划(补充)
针对斐波那契数值,动态规划思想,递归转迭代
异步任务进行的尾递归优化
function p () { return new Promise((resolve, reject) => { resolve(1) }) }
async function fibonacci (n, ac1, ac2) { (ac1 = ac1 || 0), (ac2 = ac2 || 1); let nextFun await p().then(res => { nextFun = fibonacci.bind(null, n - 1, ac2, ac1 + ac2) }) return n <= 1 ? ac2 :nextFun }