经常看到关于尾递归
这三个词,递归很多时候,都离不开我们,废话不多说,这次我们梳理一遍关于递归那些事。
在这里关于递归,这里就不赘述了,有兴趣的可以去查一查资料。
需要了解如何优化尾递归的话,我们需要从最开始讲起。
从字面理解,自然而言就是在函数的尾部返回一个函数的调用,通常来说,指的是函数执行的最后一步。
举个例子?
const fn = () => f1() || f2()
// 这里的话, f2函数有可能是尾调用,f1不可能是尾调用
为什么f1函数不是呢,我们看这个函数的等价形式?
const fn = function () {
const flag = f1()
if(flag) {
return flag
} else {
return f2()
}
}
似乎写到这里,根据尾调用定义,我们就明白了,只有f2函数是在尾部调用。
说到这里,为什么要说尾调用呢?我们事先想一想传统的递归,典型的就是首先执行递归调用,然后根据这个递归的返回值并结算结果,那么传统的递归缺点有哪些呢?
那么我们是不是可以做优化呢,这就可以涉及上面提到的尾调用,它的原理是啥呢?
“按照阮一峰老师在es6的函数扩展中的解释就是:函数调用会在内存形成一个“调用记录”,又称“调用帧”(call frame),保存调用位置和内部变量等信息。如果在函数
A
的内部调用函数B
,那么在A
的调用帧上方,还会形成一个B
的调用帧。等到B
运行结束,将结果返回到A
,B
的调用帧才会消失。如果函数B
内部还调用函数C
,那就还有一个C
的调用帧,以此类推。所有的调用帧,就形成一个“调用栈”(call stack)。“这里的“调用帧”和“调用栈”,说的应该就是“执行环境”和“调用栈”。因为尾调用时函数的最后一部操作,所以不再需要保留外层的调用帧,而是直接取代外层的调用帧,所以可以起到一个优化的作用。
从上述的描述中,我们视乎可以理解成
调用记录
。尾递归优化
,才让它不会爆栈。既然是这样子的话,尾递归的优化,取决于浏览器,那具体有哪些主流浏览器支持呢?
safari 和火狐,有兴趣的可以去了解一下,可以写个斐波那契数列数列验证一下。
既然我们知道了,很多浏览器对于尾递归的优化支持的浏览器并不多,那你会好奇,当我们使用尾递归进行优化的时候,依然出现栈溢出
的错误,那么我们如何解决呢??
我在网上看到一个不错的方案,采用的是蹦床函数?
function trampoline(f) {
while (f && f instanceof Function) {
f = f();
}
return f;
}
那么如何使用呢?
我们拿最常见的斐波那契数列来说吧
function fibonacci(n) {
if (n === 0) return 0
if (n === 1) return 1
return fibonacci(n - 1) + fibonacci(n - 2)
}
根据上面的式子,我们可以将其写成迭代形式,用一个变量去缓存它的值?
function fibonacci (n, ac1 = 0, ac2 = 1) {
return n <= 1 ? ac2 :fibonacci(n - 1, ac2, ac1 + ac2);
}
其实试过的小伙伴,会发现,当你需要求的n足够大的时候,还是会报错,类似于下面的错误信息?
// fibonacci(10000)
Uncaught RangeError: Maximum call stack size exceeded
这个时候,那么我们如何去优化呢?难道真的没有办法可以解决了吗?
这里得借鉴下别人的思路,我觉得挺不错的,这里就给出代码?
function trampoline(f) {
while (f && f instanceof Function) {
f = f();
}
return f;
}
你可以把这个函数称之为蹦床函数
, 这个函数的作用就是放回一个新的函数,我们将它们俩结合起来的话,栈溢出的问题似乎就可以解决了?
// 可以试一试噢
trampoline(fibonacci (10000))
这里的蹦床函数,我是参考别人的写法,似乎这样子写的话,不太行,我个人觉得这样子可以避免调用栈溢出,实际情况下,这样子是行不通的,哪里有行不通的,还望指出。
当然了,手动优化,可以将递归的过程改写成迭代的过程,就拿斐波那契数列这题来说,我们可以使用动态规划来完成?,O(n)完成答案的更新。
// 伪代码
F[i] = F[i-1] + F[i-2]
嗯,将一个尾递归函数转换成循环迭代函数,算是手动优化一种方式,在我们语言没有原生支持尾递归优化,那么可以考虑这种情况。
对于尾递归而言,我们需要了解优化它的原理,如果有必要的话,将递归的形式写成迭代的形式,通过迭代方式,降低重复值的计算,当然了,这个过程,有时候是比较难的,值得我们去思考。