Tail recursion in javascript - Stack Overflow

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 pile time and will not add an extra frame to the stack. That is as far as I know not the case for all pilers 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?

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 pile time and will not add an extra frame to the stack. That is as far as I know not the case for all pilers 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?

• javascript
• recursion
• tail-recursion

Share Improve this question Follow edited May 23, 2017 at 10:31 CommunityBot 111 silver badge asked Feb 28, 2015 at 10:26 Einar SundgrenEinar Sundgren 4,44399 gold badges4444 silver badges6262 bronze badges 7

• 3 Most of the votes e from the fact that it's an easily googleable question, not that it's specifically good. The code is bad, they should use setInterval() instead. – Etheryte Commented Feb 28, 2015 at 10:38
• The setTimeout is used to call your function x millisecs after the call. It's a mon pattern to execute something every x millisecs. In this case, a for loop would need to call all the setTimeout with a known delay fo each one : x * 3000. Don't know if it can result in SO as it's not a real recursion. – Hacketo Commented Feb 28, 2015 at 10:38
• @Hacketo Why do you call this "not a real recursion"? How would you clasify this and why? To me this looks like how I would implement a loop by tail-recursion in for example Erlang. – Einar Sundgren Commented Feb 28, 2015 at 10:48
• @EinarSundgren a setTimeout add a function call on the "main" stack of execution, not on the same that called it, so it's not adding stack on the latest one. (I don't know Erlang, for examples) – Hacketo Commented Feb 28, 2015 at 10:52
• @Hacketo So it is actually because of the properties of the function used? If it were to be any other, for example 'setIntervall()' as suggested, the answer would be different? As I said, I'm a JS dabbler trying to hone my skills a bit. – Einar Sundgren Commented Feb 28, 2015 at 10:56

 |  Show 2 more ments

4 Answers 4

Sorted by: Reset to default 10

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 pleted 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 ing to JavaScript in ECMAScript 6 (Harmony) and it's perhaps the most awaited feature on the list.

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 monly 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.

This is not a clear recursion. Each call of myLoop will be performed on another stack of execution (somewhat like a separate thread) and does not rely on previous calls. As in original answer:

The setTimeout() function is non-blocking and will return immediately.

There is a myLoop function, that launches a timeout and an anonymous function, that handles, what should be performed after that timeout. The value, returned by myLoop() (which will be undefined) is not used later in the calls.

Currently, tail recursion is not supported in most JS runtimes. Therefore unless you know exactly which runtime your code will be running, it will not be safe to rely on tail recursion to avoid "Maximum call stack size exceeded" error.

It is not supported in Node (with the exception of versions >6.4 & <8 where it can be enabled with a flag).

Safari versions 11 and 12 also appear to support it, but no other major browsers do.

Dr. Axel Rauschmayer has mentioned on his blog 2ality on 2018-05-09 that widespread support may never e.