Why Does A Function With Settimeout Not Lead To A Stack Overflow

I was writing a test for handling huge amounts of data. To my surprise, if I added a setTimeout to my function, it would no longer lead to a stack overflow (how appropriate for thi

Solution 1:

Because it is no longer recursive. At least not technically.

The source code does look recursive so a programmer may write such code as if it is recursive but from the point of view of the CPU it is no longer recursive. It is processed sequentially in a loop.

Recursion and the stack

A recursive function calls itself. What happens when this happens is that the stack keeps increasing until the last function returns. A function's stack frame isn't removed from the stack until the function returns (let's ignore closures for now) so because recursive function calls itself it won't return until that call to itself returns. This is what causes the stack to grow.

Tail recursion

Languages such as Lisp, Haskell and Scala recognize that there are some cases where a stack frame can be released while doing recursion. Generally, if the recursive call is the last instruction in the function and no other processing is done to the return value you can remove the current stack frame because it will no longer be used after the recursive function returns. Therefore, such languages implement what's called tail recursion: the ability to recurse infinitely without growing the stack.

This is especially useful for very pure functional languages where the only programming structure you have is functions because without the existence of statements you cannot have loop statements or conditional statements etc. Tail recursion makes infinite loops in Lisp possible.

However, Javascript does not have tail recursion. So this does not affect how recursion behaves in Javascript. I mention this to note that not all recursion need to grow the stack.

Scheduling

Timer functions such as setTimeout() and setInterval() does not call the functions passed to them. Not only do they not call them immediately, they don't call them at all. All they do is pass the function to the event loop along with information of when should the function be called.

The event loop is essentially the core of javascript. The interpreter enters the event loop if and only if there is no more javascript to execute. You can think of the event loop as the idle state of the interpreter. The event loop continuously checks for events (I/O, UI, timer etc.) and execute the relevant functions attached to the event. This is the function you passed to setTimeout().

setTimeout

So with the facts given above we can see how "recursion" via setTimeout is not really recursion.

1. First your function calls setTimeout and passes itself to it.

2. setTimeout saves the function reference to a list of event listeners and sets up the timer to trigger the event which will trigger the function

3. Your function continues and returns, note that the "recursed" function is not yet called. Since your function returns it's stack frame gets removed from the stack.

4. Javascript enters the event loop (there's no more javascript to process).

5. Timer for your function expires and the event loop calls it. Repeat until you stop calling setTimeout

Solution 2:

The first one is not recursive (although it looks like it, at a first glance).

Let's simplify and imagine a recursive method f and we limit the call depth to 5. The second example is recursive, something like

f(){ f(){ f(){ f(){ f(){ }}}}}

With the other example, we create 5 timeouts with f as the call back (the array is not totally accurate, it's more like a priority queue with your random timeout value - but this abstraction helps understanding the problem)

[f, f, f, f, f]

javascript is not multithreaded so all 5 functions are called one after the other. Eventually, a function will create another timeout, and when that happens, the new f callback is added to the list (or queue).

So basically, timeout serializes the recursion here. Beware that in this case f will be called almost 2 million times, because all but the last will add another f to the list which get's executed also.