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?