尾递归优化的JavaScript？ [英] Tail Recursion optimization for JavaScript?

问题描述

我道歉，大家的这种含糊其辞的previous版本。有人决定把可怜的新来的女孩，帮我改写了这个问题 - 在这里就是我希望能澄清事实的更新（和，感谢所有那些谁如此慷慨的答案为止）：

My apologies to everyone for previous versions of this being vague. Someone has decided to have pity on the new girl and help me rewrite this question - here's an update that I hope will clear things up (and, thanks to all those who have been so generous with answers so far):

问题

我是一个新的计算机专业的学生，​​我在大学的第一年。对于我的算法类项目的最后，我们可以挑选任何我们想要的语言并实施了求精/效率，即发现本机（内部？）的另一种语言的算法，但在我们选择的语言缺少的。

I'm a new computer science student, in my first year at Uni. For the final project for my Algorithms class, we can pick any language we would like and implement a "refinement"/"efficiency" algorithm that is found natively (internally?) in another language, but missing in the language we pick.

我们最近刚刚在课堂上学习递归和我的教授简要地提到了JavaScript不执行尾递归。从我的研究网络，新的ECMA脚本6规格有这个功能，但它不是在任何（/最？）的JavaScript版本/引擎在present？ （抱歉，如果我不知道哪个是哪个了...我在这个新的）。

We just recently studied recursion in class and my professor briefly mentioned that JavaScript does not implement Tail Recursion. From my research online, the new ECMA script 6 specification includes this feature, but it's not in any(/most?) JavaScript versions/engines at present? (sorry if I'm not sure which is which... I'm new at this).

• 我没有找到像<一一些有趣的帖子href="http://taylodl.word$p$pss.com/2013/06/07/functional-javascript-tail-call-optimization-and-trampolines/">this.

和另一个<一href="http://stackoverflow.com/questions/3660577/are-any-javascript-engines-tail-call-optimized">Stack溢出的问题： http://stackoverflow.com/questions/3660577/are-any-javascript-engines-tail-call-optimized

最后，什么是一个非常酷的ECMA脚本6模拟器名为<一个href="http://bbenvie.com/articles/2013-01-06/JavaScript-ES6-Has-Tail-Call-Optimization">Continuum

And finally, what is a really cool ECMA Script 6 emulator called Continuum

我的任务是提供2个选项周边（编码A）工作，即缺乏功能。

My assignment is to provide 2 options for (coding a) WORK AROUND to the feature that is lacking.

所以，我的问题是......没有任何人，更聪明，经验丰富，比我，有我怎么可能实现的任何想法或例子：

So, my question is... does anyone, far more intelligent and experienced than I, have any thoughts or examples on how I might implement a:

解决作为缺乏尾递归优化？

WORK AROUND for the lack of Tail Recursion Optimization?

推荐答案

递归的一个可能的优化是懒惰地评估，也就是，返回计算（=函数），将返回，而不是计算和返回它的值立竿见影。

One possible optimization of recursion is to evaluate lazily, that is, return a "computation" (=function) that will return a value instead of computing and returning it straight away.

考虑一个函数，总结了数字（在一个相当愚蠢的方式）：

Consider a function that sums up numbers (in a rather silly way):

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

如果你把它叫做

N = 100000 将超过栈（至少在我的铬）。要应用该优化，先将其转换为真正的尾递归，所以该函数返回只需要打一个电话给自己，仅此而已：

If you call it with n = 100000 it will exceed the stack (at least, in my Chrome). To apply the said optimization, first convert it to true tail-recursive, so that the function returns just a call to itself and nothing more:

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

和包装这个直接自呼与懒惰的功能：

and wrap this direct self-call with a "lazy" function:

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

现在，为了获得这个结果，我们重复计算直到它返回一个非功能：

Now, to obtain the result from this, we repeat the computation until it returns a non-function:

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

该版本有没有问题，N = 100000，百万等

This version has no problems with n = 100000, 1000000 etc

这篇关于尾递归优化的JavaScript？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！