在javascript中的尾递归

Question

我在JS方面不是很有经验.但是,作为大多数人,我有时需要在浏览器中添加一些额外的功能.

在寻找其他问题的答案时,我在SO处找到了这个答案.答案和响应者都受到高度评价,按照SO标准,这意味着它们非常可靠.引起我注意的是,在"neatened up"变体中,它使用尾递归来循环函数:

(function myLoop (i) {          
   setTimeout(function () {   
      alert('hello');          //  your code here                
      if (--i) myLoop(i);      //  decrement i and call myLoop again if i > 0
   }, 3000)
})(10);     

从我的角度看,这看起来像糟糕的工程.使用递归来解决命令式/ OO语言中的非递归问题就是要求麻烦.十次或100次迭代应该是安全的.但是10000或无限循环呢？在像Erlang和Haskell这样的纯函数式语言中,我知道尾递归在编译期间被转换为循环,并且不会向堆栈添加额外的帧.据我所知,对于例如C/C++或Java的所有编译器而言,情况并非如此.

JS怎么样？在没有SO风险的情况下使用尾递归是否安全？或者这取决于脚本运行的实际解释器？

Answer 1

您提供的示例没有任何尾递归.考虑:

(function loop(i) {
    setTimeout(function main() {
        alert("Hello World!");
        if (i > 1) loop(i - 1);
    }, 3000);
}(3));

1. 我给了内部函数名称main和外部函数名称loop.
2. loop使用该值立即调用该函数3.
3. 该loop功能只做一件事.它调用setTimeout然后返回.
4. 因此,呼叫setTimeout是尾调用.
5. 现在,main在3000几毫秒之后由JavaScript事件循环调用.
6. 何时main被调用loop并setTimeout完成执行.
7. 该main函数有条件地调用loop减少的值i.
8. 当main调用loop,它是一个尾调用.
9. 但是,无论是递归100次还是10000次都没关系,堆栈大小永远不会增加太多而导致溢出.原因是当你使用时setTimeout,loop函数会立即返回.因此,main被调用的时间loop不再在堆栈上.

一个直观的解释:

|---------------+ loop (i = 3)
                |---------------+ setTimeout (main, 3000)
                                |
                |---------------+ setTimeout return
|---------------+ loop return
~
~ 3000 milliseconds
~
|---------------+ main (i = 3)
                |---------------+ alert ("Hello World!")
                                |
                |---------------+ alert return
                | i > 1 === true
                |---------------+ loop (i = 2)
                                |---------------+ setTimeout (main, 3000)
                                                |
                                |---------------+ setTimeout return
                |---------------+ loop return
|---------------+ main return
~
~ 3000 milliseconds
~
|---------------+ main (i = 2)
                |---------------+ alert ("Hello World!")
                                |
                |---------------+ alert return
                | i > 1 === true
                |---------------+ loop (i = 1)
                                |---------------+ setTimeout (main, 3000)
                                                |
                                |---------------+ setTimeout return
                |---------------+ loop return
|---------------+ main return
~
~ 3000 milliseconds
~
|---------------+ main (i = 1)
                |---------------+ alert ("Hello World!")
                                |
                |---------------+ alert return
                | i > 1 === false
|---------------+ main return

这是发生了什么:

1. 首先,loop(3)在调用3000返回后调用并返回毫秒main.
2. 该main函数调用loop(2)和3000毫秒后返回main时再次调用.
3. 该main函数调用loop(1)和3000毫秒后返回main时再次调用.

因此,堆栈大小永远不会无限增长,因为setTimeout.

阅读以下问题和答案以获取更多详细信息:

延续和回调之间有什么区别？

希望有所帮助.

PS尾部调用优化将在ECMAScript 6(Harmony)中用于JavaScript,它可能是列表中最受期待的功能.

Answer 2

该代码本身不是递归的,恰恰相反,它使用延续传递来消除尾调用.这是一个没有的例子setTimeout:

// naive, direct recursion

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

try {
  sum_naive(50000)
} catch(e) {
  document.write(e + "<br>")
}


// use CPS to optimize tail recursive calls

function sum_smart(n) {
  
  function f(s, n) {
    return n == 0 ? s : function() { return f(s+n, n-1) };
  }
  
  var p = f(0, n)
  
  while(typeof p == "function")
    p = p()
    
  return p;
}

document.write(sum_smart(50000) + "<br>")

CPS通常用于不支持开箱即用的语言中的尾递归优化.Javascript setTimeout基本上采用当前的延续并将其"抛出"到主线程.一旦主线程准备就绪,它"捕获"延续并在恢复的上下文中运行代码.