javascript - JavaScript 的尾递归优化？

Question

对于之前版本的含糊不清，我向大家道歉。有人决定同情这个新来的女孩并帮助我重写这个问题 - 这是我希望能解决问题的更新(并且，感谢所有到目前为止一直慷慨回答的人):

---

问题

我是一名新的计算机科学专业的学生，​​在我大学的第一年。对于我的算法类的最终项目，我们可以选择任何我们喜欢的语言并实现一个“精炼”/“效率”算法，该算法在另一种语言中 native (内部？)，但在我们选择的语言中缺失。

我们最近刚刚在类里面学习了递归，我的教授简要地提到了 JavaScript 没有实现尾递归。根据我的在线研究，新的 ECMA 脚本 6 规范包含此功能，但目前在任何(/大多数？)JavaScript 版本/引擎中都没有？ (抱歉，如果我不确定哪个是哪个......我是新手)。

• 我确实发现了一些有趣的帖子，例如 this .

• 还有一个Stack Overflow question: https://stackoverflow.com/questions/3660577/are-any-javascript-engines-tail-call-optimized

• 最后，什么是非常酷的 ECMA Script 6 模拟器 Continuum

我的任务是提供 2 个选项，用于(编码 a)WORK AROUND 缺少的功能。

所以，我的问题是......有没有比我聪明和经验丰富的人对我如何实现有任何想法或例子:

解决方法缺少尾递归优化？

Answer 1

递归的一种可能的优化是惰性求值，即返回一个“计算”(=函数)，它将返回一个值，而不是立即计算并返回它。

考虑一个对数字求和的函数(以一种相当愚蠢的方式):

function sum(n) {
    return n == 0 ? 0 : n + sum(n - 1)
}

如果您使用 n = 100000 调用它，它将超出堆栈(至少在我的 Chrome 中)。要应用上述优化，首先将其转换为真正的尾递归，以便该函数仅返回对其自身的调用，仅此而已:

function sum(n, acc) {
    return n == 0 ? acc : sum(n - 1, acc + n)
}

并用一个“惰性”函数包装这个直接的 self 调用:

function sum(n, acc) {
    return n == 0 ? acc : function() { return sum(n - 1, acc + n) }
}

现在，为了从中获得结果，我们重复计算直到它返回一个非函数:

f = sum(100000, 0)
while(typeof f == "function")
    f = f()

此版本在 n = 100000、1000000 等方面没有问题