Avoiding stack overflow by using setTimeout

Question

I've found the following question here:

The following recursive code will cause a stack overflow if the array list is too large. How can you fix this and still retain the recursive pattern?

And the answer:

The potential stack overflow can be avoided by modifying the nextListItem function as follows:

var list = readHugeList();

var nextListItem = function() {
    var item = list.pop();

    if (item) {
        // process the list item...
        setTimeout( nextListItem, 0);
    }
};

The stack overflow is eliminated because the event loop handles the recursion, not the call stack. When nextListItem runs, if item is not null, the timeout function (nextListItem) is pushed to the event queue and the function exits, thereby leaving the call stack clear. When the event queue runs its timed-out event, the next item is processed and a timer is set to again invoke nextListItem. Accordingly, the method is processed from start to finish without a direct recursive call, so the call stack remains clear, regardless of the number of iterations.

Can somebody please explain to me:

1. whether this use case is ever practical
2. why long array can cause stack overflow

Answer 1

This is just a hacky alternative to trampolines, which in turn are just a hacky alternative to TCO.

When you call a function in Javascript, you add a frame to the call stack. That frame contains information about the variables in the scope of the function and how it was called.

Before we call a function, the call stack is empty.

-------

If we call function foo, then we add a new frame to the top of the stack.

| foo |
-------

When foo finishes executing, we pop the frame off the stack again, leaving it empty again.

Now, if foo in turn calls another function bar, then we'll need to add a new frame onto the stack, whilst foo is executing.

| bar |
| foo |
-------

Hopefully you can see that if a function calls itself recursively it keeps adding new frames to the top of the call stack.

| ...          |
| nextListItem |
| nextListItem |
| nextListItem |
| nextListItem |
----------------

Recursive functions will keep adding frames until either they finish processing, or they exceed the max length of the call stack, resulting in an overflow.

Because setTimeout is an asynchronous operation, it doesn't block your function, which means nextListItem will be allowed to finish and its frame can be popped off the call stack—preventing it from growing. The recursive call will be handled with the event loop instead.

Is this pattern ever useful? The max size for the call stack depends on your browser, but it can be as low as 1130. If you wanted to process an array with a few thousand elements using a recursive function, then you'd risk blowing the call stack.

Trampolines use a similar technique, but rather than offloading the work to the event loop, you return a function which calls the next iteration instead, then the calls can be managed with a while loop (which doesn't affect the stack).

var nextListItem = function() {
  var item = list.pop();

  if (item) {
    // process the list item...
    return nextListItem;
  }
};

while(recur = recur()) {}

Answer 2

1. It normally isn't, but in the off chance you decide you need to recursively chain the same function call for long sequences this could come in handy.

2. Stack overflow during recursive operations occurs when the amount of stack memory allocated for a particular program has been fully utilized. A sufficiently long array that is traversed recursively can cause a stack overflow. Perhaps you do not understand how the call stack works?

Answer 3

The repeating for loop is the most efficient for the code posted. However, if your actual code cannot be fitted to using a for loop, then there is another alternative.

The use of setTimeout depends on your opinion of 'practical,' so let's just list the facts so you can decide for yourself.

• setTimeout forces the browser to swamp the CPU with operations to get millisecond precision timing. This can be very power inefficient.
• With setTimeout, every iteration will cost 4ms. Just 4 iterations will take the time for a whole frame to get rendered. 250 iterations, and a whole second goes by.

But there is an alternative to setTimeout that will help you achieve exactly what you are trying to do without using setTimeout: the DeferStackJS library. If you use DeferStackJS, then all you would need to do is as follows.

var list = readHugeList();

var nextListItem = function() {
    var item = list.pop();

    if (item) {
        // process the list item...
        DeferStack( nextListItem );
    }
};

Please emphasize that the above snippet of code is intended for demonstrating how to integrate DeferStackJS. Truth be told, using either DeferStackJS or Array.prototype.pop would be very inappropriate for this specific snippet of code. Instead, the following code would beat both of them hands down.

var list = readHugeList();

var nextListItem = function() {
    "use strict";
    var item, i = list.length;
    while (i--) { // Bounds check: as soon as i === -1, the while loop will stop.
                  // This is because i-- decrements i, returning the previous
                  // value of i
        item = list[i];
        if (!item) break; // break as soon as it finds a falsey item 
        // Place code here to be executed if it found a truthy value:

        // process the list item...
    }
    if (i !== -1) {
        // Place code here to be executed if it found a falsey value:

    }
};

The only reason DeferStackJS is mentioned is because I am a firm believer in that the #1 duty of a person answering a forum is to answer the original question asked. Then after they answer that they can put up commentary second-guessing the question about what was intended to be asked like this.