尾调优化
在知道尾递归之前, 我们要直到什么是尾调用优化, 因为尾调用优化是尾递归的基础. 尾调用就是: 在函数的最后一步调用另一个函数.
- function f() { return g()
- }
ps: 最后一步必须是之久调用另一函数, 而不能是一个常量或是一个表达式, 如 return y 或 return g() + 1
尾调用优化的原理是什么?
按照阮一峰老师在 es6 的函数扩展 http://es6.ruanyifeng.com/#docs/function 中的解释就是: 函数调用会在内存形成一个 "调用记录", 又称 "调用帧"(call frame), 保存调用位置和内部变量等信息. 如果在函数 A 的内部调用函数 B, 那么在 A 的调用帧上方, 还会形成一个 B 的调用帧. 等到 B 运行结束, 将结果返回到 A,B 的调用帧才会消失. 如果函数 B 内部还调用函数 C, 那就还有一个 C 的调用帧, 以此类推. 所有的调用帧, 就形成一个 "调用栈"(call stack).
这里的 "调用帧" 和 "调用栈", 说的应该就是 "执行环境" 和 "作用域链". 因为尾调用时函数的最后一部操作, 所以不再需要保留外层的调用帧, 而是直接取代外层的调用帧, 所以可以起到一个优化的作用.
尾递归优化
我们知道, 递归虽然使用起来方便, 但是递归是在函数内部调用自身, 当递归次数达到一定数量级的时候, 他形成的调用栈的深度是很可怕的, 很可能会发生 "栈溢出" 错误. 尾递归优化, 就是利用尾调用优化的原理, 对递归进行优化. 举一个很常见的例子:
求斐波那契数值
- function fibonacci (n) {
- return n <= 1 ? 1 : fibonacci(n - 1) + fibonacci(n - 2);
- }
此函数没有进行任何的优化, 当我们在控制台去执行此函数的时候, fibonacci(40) 就已经出现了明显的响应慢的问题, fibonacci(50) 的时候浏览器卡死. 2. 优化
- function fibonacci (n, ac1, ac2) {
- (ac1 = ac1 || 1), (ac2 = ac2 || 1);
- return n <= 1 ? ac2 :fibonacci(n - 1, ac2, ac1 + ac2);
- }
此优化有两个点: 首先进行了算法上的优化, 减少了很多重复的计算, 时间复杂度大大降低; 第二进行了尾递归优化, 按理说不会发生 "栈溢出". 我们可以到控制台中再尝试, 发现速度的提升不是一般的快, 证明第一个优化生效了, 但是当我们允许 fibonacci(10000) 的时候, 报错了:
Uncaught RangeError: Maximum call stack size exceeded
, 这就说明我们的尾递归优化并没有生效. 为什么呢?
局限性
上面说到, 我们直接再浏览器的控制台中执行 fibonacci(10000) 的时候, 发生了栈溢出, 这是为什么呢? 关于这一点, 我目前查阅资料之后的理解就是, 虽然 es6 已经提出了要实现尾递归优化, 但是真正落地实现了尾递归优化的浏览器并不多. 所以当我们使用尾递归进行优化的时候, 依旧发生了 "栈溢出" 的错误.
蹦床函数
那怎么办呢? 我们还有另一个方法去达到尾递归优化的效果, 那就是使用
蹦床函数 (trampoline)
- .
- function trampoline(f) {
- while (f && f instanceof Function) {
- f = f();
- }
- return f;
- }
代码修改为返回一个新函数.
- function fibonacci (n, ac1, ac2) {
- (ac1 = ac1 || 1), (ac2 = ac2 || 1);
- return n <= 1 ? ac2 :fibonacci.bind(null, n - 1, ac2, ac1 + ac2);
- }
两个函数结合就可以将递归状态为循环, 栈溢出的问题也就解决了.
- trampoline(fibonacci (100000))
- // Infinity
来源: https://juejin.im/entry/5b3aecc06fb9a024a23f72be