JavaScript尾递归优化探索

sean 发布于2019-08-22 18:27 / 2771人阅读

摘要：原文地址尾调优化在知道尾递归之前，我们要直到什么是尾调用优化，因为尾调用优化是尾递归的基础。尾递归优化，就是利用尾调用优化的原理，对递归进行优化。所以当我们使用尾递归进行优化的时候，依旧发生了栈溢出的错误。

原文地址：https://github.com/HolyZheng/...

尾调优化

在知道尾递归之前，我们要直到什么是尾调用优化，因为尾调用优化是尾递归的基础。尾调用就是：在函数的最后一步调用另一个函数。

function f() {
  return g()
}

ps：最后一步必须是之久调用另一函数，而不能是一个常量或是一个表达式，如 return y 或 return g() + 1

尾调用优化的原理是什么？

按照阮一峰老师在es6的函数扩展中的解释就是：函数调用会在内存形成一个“调用记录”，又称“调用帧”（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)的时候浏览器卡死。
优化

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

服务器托管 GPU服务器优化递归数据栈 javascript优化 JavaScript代码优化尾队列

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/95881.html

ES6函数与Lambda演算

摘要：高阶函数函数式编程中，接受函数作为参数，或者返回一个函数作为结果的函数通常就被称为高阶函数。均属于高阶函数，高阶函数并不神秘，我们日常编程也会用到。参考演算函数式编程指南入门康托尔哥德尔图灵永恒的金色对角线原文函数与演算缘起造了一个轮子，根据GitHub项目地址，生成项目目录树，直观的展现项目结构，以便于介绍项目。欢迎Star。 repository-tree 技术栈： ES6 ...

fasss 2019-08-21 18:45 评论0 收藏0
ES6被你忽略的尾调用

摘要：被你忽略的尾调用尾调用是什么在有一个新特性尾调用用最简单的一句话描述就是某个函数的最后一步再调用另一个函数，听起来挺简单的，但是它的功能特别强大，直接给你撸个例子吧。如果函数内部还调用函数，那就还有一个的调用记录栈，以此类推。 title: 被你忽略的‘尾调用’date: 2017-05-02 16:52:22 tags: [ES6,javascript] 尾调用是什么？在ES6有...

xeblog 2019-08-22 11:04 评论0 收藏0
用 JavaScript 实现链表操作 - 08 Remove Duplicates

摘要：递归版本尾递归很多递归没办法自然的写成尾递归，本质原因是无法在多次递归过程中维护共有的变量，这也是循环的优势所在。这是因为虽然用的，但并没有开启尾递归优化。 TL;DR 为一个已排序的链表去重，考虑到很长的链表，需要尾调用优化。系列目录见前言和目录。需求实现一个 removeDuplicates() 函数，给定一个升序排列过的链表，去除链表中重复的元素，并返回修改后的链表。理想...

Me_Kun 2019-08-21 15:04 评论0 收藏0
js 实现斐波那契数列(数组缓存、动态规划、尾调用优化)

摘要：根据该规则，返回第个斐波那契数。尾递归函数调用自身，称为递归。一个前端眼中的斐波那契数列解斐波那契数列的实用解法调用栈尾递归和手动优化尾调用优化译我从用写斐波那契生成器中学到的令人惊讶的件事斐波那契数列是以下一系列数字： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在种子数字 0 和 1 ...

赵连江 2019-08-23 11:38 评论0 收藏0
翻译连载 | 第 9 章：递归（下）－《JavaScript轻量级函数式编程》 |《你不知道的JS》

摘要：每个函数调用都将开辟出一小块称为堆栈帧的内存。当第二个函数开始执行，堆栈帧增加到个。当这个函数调用结束后，它的帧会从堆栈中退出。保持堆栈帧跟踪函数调用的状态，并将其分派给下一个递归调用迭。原文地址：Functional-Light-JS 原文作者：Kyle Simpson－《You-Dont-Know-JS》作者关于译者：这是一个流淌着沪江血液的纯粹工程：认真，是 HTM...

LeviDing 2019-08-21 16:44 评论0 收藏0