Tail recursion in javascript

Question

I'm not very experienced in JS. But as most people I sometimes have the need to add some extra functionality to a browser.

When looking for answers to other questions I came upon this answer at SO. The answer and the responder are highly upvoted, and by SO standards it means they are pretty reliable. What caught my attention is that in the "neatened up" variation it uses tail recursion to loop the function:

(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);     

From my perspective this looks like bad engineering. Using recursion to solve non recursive problems in an imperative/OO language is to ask for trouble. Ten or 100 iterations should be safe. But what about 10000 or an infinite loop? In purely functional languages as Erlang and Haskell I know that tail recursions are converted to loops during compile time and will not add an extra frame to the stack. That is as far as I know not the case for all compilers of for example C/C++ or Java.

How about JS? Is it safe to use tail recursion there without the risk of an SO? Or will this depend on the actual interpreter the script runs on?

Answer 1

The example you provided does not have any tail recursion. Consider:

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

1. I've given the inner function the name main and the outer function the name loop.
2. The loop function is immediately invoked with the value 3.
3. The loop function only does one thing. It invokes setTimeout and then returns.
4. Hence, the call to setTimeout is a tail call.
5. Now, main is called by the JavaScript event loop after 3000 milliseconds.
6. When main is called both loop and setTimeout have completed execution.
7. The main function conditionally calls loop with a decremented value of i.
8. When main calls loop, it is a tail call.
9. However, it doesn't matter whether you recurse 100 times or 10000 times, the stack size will never increase so much to cause an overflow. The reason is that when you use setTimeout, the loop function immediately returns. Hence, by the time main is called loop is no longer on the stack.

A visual explanation:

|---------------+ 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

Here's what's happening:

1. First, loop(3) is called and 3000 milliseconds after it returns main is called.
2. The main function calls loop(2) and 3000 milliseconds after it returns main is called again.
3. The main function calls loop(1) and 3000 milliseconds after it returns main is called again.

Hence, the stack size never grows indefinitely because of setTimeout.

Read the following question and answer for more details:

What's the difference between a continuation and a callback?

Hope that helps.

P.S. Tail call optimization will be coming to JavaScript in ECMAScript 6 (Harmony) and it's perhaps the most awaited feature on the list.

Answer 2

That code is not recursive per se, quite the contrary, it uses continuation passing to eliminate tail calls. Here's an example without 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 is commonly used for tail recursion optimization in languages that don't support it out of the box. Javascript's setTimeout basically takes the current continuation and "throws" it to the main thread. Once the main thread is ready, it "catches" the continuation and runs the code in the restored context.