Recursive calls cause call stack to overflow but not event queue?

Question

I recently came across this snippet of code:

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?

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

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

The answer was:

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

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

Explanation: 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.

So, the overhead of the call stack was being handled by the event queue? Is there a maximum number of events after which the event queue cannot take any more events and how does that number compare to the call stack's limit of the function calls it can stack? Also, is there an alternative way to achieve the same thing?

Answer 1

So, the overhead of the call stack was being handled by the event queue?

Not exactly. There is only one event queued at a time. The difference is that it forgets where it was scheduled from - if it had to retain that information, it would run out of memory as well.

For the recursion, the compiler/interpreter may do a similar thing, throwing away the no longer needed call stack as tail call optimisation. The Safari browser has implemented this, for example.

Also, is there an alternative way to achieve the same thing?

A loop, of course :-)

function nextListItem = function() {
    for (var item = list.pop(), item, item = list.pop()) {
        // process the list item...
    }
}

How can you fix this and still retain the recursive pattern?

You can use trampolining to do the TCO manually.

function call(run) {
    return { done: false, run };
}
function stop(value) {
    return { done: true, value };
}
function runTrampoline(cont) {
    while (!cont.done) cont = cont.run();
    return cont.value;
}

var list = readHugeList();
function nextListItem() {
    return runTrampoline(nextListItemT());
}
function nextListItemT() {
    var item = list.pop();
    if (item) {
        // process the list item...
        return call(nextListItemT);
    } else {
        return stop();
    }
}