JavaScript的尾递归优化？

Question

我向所有人道歉,因为以前版本的这个模糊不清.有人决定对这个新女孩表示同情并帮我改写这个问题 - 这是一个我希望能够解决问题的更新(并且,感谢迄今为止所有那些慷慨解答的人):

---

问题

我是Uni的第一年,我是一名新的计算机科学专业的学生.对于我的算法类的最终项目,我们可以选择我们想要的任何语言,并实现一种"细化"/"效率"算法,该算法在本地(内部？)用另一种语言找到,但在我们选择的语言中缺失.

我们刚刚在课堂上研究了递归,我的教授简要地提到JavaScript没有实现Tail Recursion.从我的在线研究中,新的ECMA脚本6规范包含此功能,但它目前不在任何(/大多数？)JavaScript版本/引擎中？(对不起,如果我不确定哪个是......我是新来的).

• 我确实发现了一些有趣的职位像这样.

• 另一个Stack Overflow问题:/sf/ask/256240421/

• 最后,什么是一个非常酷的ECMA Script 6仿真器,名为Continuum

我的任务是为缺少的功能提供2个(编码)WORK AROUND的选项.

所以,我的问题是......是否有人,比我更聪明,更有经验,对我如何实现以下方面有任何想法或例子:

解决了缺乏尾递归优化？

Answer 1

一种可能的递归优化是懒惰地评估,即返回一个"计算"(=函数),它将返回一个值而不是计算并立即返回它.

考虑一个总结数字的函数(以一种相当愚蠢的方式):

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

如果你用n =调用它,100000它将超过堆栈(至少在我的Chrome中).要应用所述优化,首先将其转换为true tail-recursive,以便该函数仅返回对自身的调用,仅此而已:

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

并使用"懒惰"函数包装此直接自调用:

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等

Answer 2

正如我在评论中提到的,您总是可以将程序转换为延续传递样式,然后使用异步函数调用来实现真正的尾部调用优化.为了推动这一点,请考虑以下示例:

function foldl(f, a, xs) {
    if (xs.length === 0) return a;
    else return foldl(f, f(a, xs[0]), xs.slice(1));
}

显然这是一个尾递归函数.所以我们需要做的第一件事就是将它转换为延续传递样式,这非常简单:

function foldl(f, a, xs, k) {
    if (xs.length === 0) k(a);
    else foldl(f, f(a, xs[0]), xs.slice(1), k);
}

而已.我们的功能现在是延续传递风格.然而,仍然存在一个大问题 - 没有尾部调用优化.但是,使用异步函数可以轻松解决这个问题:

function async(f, args) {
    setTimeout(function () {
        f.apply(null, args);
    }, 0);
}

我们的尾调用优化foldl函数现在可以写成:

function foldl(f, a, xs, k) {
    if (xs.length === 0) k(a);
    else async(foldl, [f, f(a, xs[0]), xs.slice(1), k]);
}

现在你需要做的就是使用它.例如,如果要查找数组的数字总和:

foldl(function (a, b) {
    return a + b;
}, 0, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], function (sum) {
    alert(sum); // 55
});

把它们放在一起:

function async(f, args) {
    setTimeout(function () {
        f.apply(null, args);
    }, 0);
}

function foldl(f, a, xs, k) {
    if (xs.length === 0) k(a);
    else async(foldl, [f, f(a, xs[0]), xs.slice(1), k]);
}

foldl(function (a, b) {
    return a + b;
}, 0, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], function (sum) {
    alert(sum); // 55
});

当然,继续传递风格是用JavaScript编写的一种痛苦.幸运的是,有一种叫做LiveScript的非常好的语言,可以让回调更加有趣.用LiveScript编写的相同函数:

async = (f, args) ->
    setTimeout ->
        f.apply null, args
    , 0

foldl = (f, a, xs, k) ->
    if xs.length == 0 then k a
    else async foldl, [f, (f a, xs.0), (xs.slice 1), k]

do
    sum <- foldl (+), 0, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    alert sum

是的,这是一种编译成JavaScript的新语言,但值得学习.特别是因为回调(即<-)允许您轻松编写回调而无需嵌套函数.

Answer 3

许多最常见的语言缺乏尾递归优化，因为它们根本不希望您使用递归来解决线性问题。

仅当递归调用是函数执行的最后一件事时才适用尾递归优化，这意味着不需要查看当前堆栈内容，因此无需通过添加另一个堆栈帧来保留它。

任何这样的算法都可以改编成迭代形式。例如（伪代码）：

 int factorial(int x) {
      return factTail(x,1);
 }

 int factTail(int x, int accum) {
      if(x == 0) {
          return accum;
      } else {
          return(factTail (x-1, x * accum);
      }
 }

...是一个factorial()经过定制的实现，以确保最后一个语句返回递归调用的结果。了解 TCO 的引擎会对此进行优化。

以相同顺序执行操作的迭代版本：

  int factorial(int x) {
      int accum = 1;
      for(int i=x; i>0; i--) {
          accum *= i;
      }
      return accum;
 }

（我让它向后计数以近似递归版本的执行顺序——实际上，您可能不会对阶乘执行此操作）

如果您知道递归深度不会很大（在本例中， 的值很大x），那么使用递归调用就可以了。

通常，递归会产生非常优雅的解决方案规范。摆弄算法来获得尾调用会损害这一点。看看上面的内容factorial比经典的更难理解：

 int factorial(int x) {
     if(x == 1) {
         return 1;
     } else {
         return factorial(x-1) * x;
     }
 }

...然而，对于不需要堆栈的任务来说，这种经典形式非常需要堆栈。因此可以说迭代形式是解决这个特定问题的最清晰的方法。

由于编程的教学方式，如今大多数程序员对迭代形式比递归方法更熟悉。您是否遇到了特定的递归算法问题？