Workaround for lack of "tail call optimization" in JS

example.js

// Lack of tail call optimization in JS
var sum = function(x, y) {
  return y > 0 ? sum(x + 1, y - 1) :
         y < 0 ? sum(x - 1, y + 1) :
         x
}

sum(20, 100000) // => RangeError: Maximum call stack size exceeded

// Using workaround
var sum = tco(function(x, y) {
  return y > 0 ? sum(x + 1, y - 1) :
         y < 0 ? sum(x - 1, y + 1) :
         x
})
sum(20, 100000) // => 100020

tail-call-optimization.js

function tco(f) {
  /**
  Takes `f` function and returns wrapper in return, that may be
  used for tail recursive algorithms. Note that returned funciton
  is not side effect free and should not be called from anywhere
  else during tail recursion. In other words if
  `var f = tco(function foo() { ... bar() ... })`, then `bar`
  should never call `f`. It is ok though for `bar` to call `tco(foo)`
  instead.

  ## Examples
  var sum = tco(function(x, y) {
    return y > 0 ? sum(x + 1, y - 1) :
           y < 0 ? sum(x - 1, y + 1) :
           x
  })
  sum(20, 100000) // => 100020
  **/

  var value, active = false, accumulated = []
  return function accumulator() {
    // Every time accumulator is called, given set of parameters
    // are accumulated.
    accumulated.push(arguments)
    // If accumulator is inactive (is not in the process of
    // tail recursion) activate and start accumulating parameters.
    if (!active) {
      active = true
      // If wrapped `f` performs tail call, then new set of parameters will
      // be accumulated causing new iteration in the loop. If `f` does not
      // performs tail call then accumulation is finished and `value` will
      // be returned. 
      while (accumulated.length) value = f.apply(this, accumulated.shift())
      active = false
      return value
    }
  }
}

@jdalton:

    result = fn.apply(this, [nextArgs, nextArgs = null][0]);

creates a gratuitous array literal. How about just putting nextArgs = null; on its own line?

/be

@BrendanEich current version build on @jdalton array suggestion but in slightly diff way avoiding that.

@BrendanEich

The reason that version uses an array is because nextArgs needs to be falsey before fn.apply(...) is executed and I didn't want to juggle another variable just for that purpose.
Putting nextArgs = null; on its own line would either kill the args passed to fn.apply(...) causing the loop to exit early

while (nextArgs) {
  nextArgs = null;
  result = fn.apply(this, nextArgs);
}

or null nextArgs too late causing the loop to exit early as well

while (nextArgs) {
  result = fn.apply(this, nextArgs);
  nextArgs = null;
}

@Gozala's original version used the variable args just for this juggle

while (nextArgs) {
  args = nextArgs;
  nextArgs = null;
  result = fn.apply(this, args);
}

@jdalton: right, I should have acknowledged that -- two extra lines. Still, seems worth avoiding an array per iteration of the while.

@Gozala: thanks!

/be

I created a jsPerf of the variations here as well as non-recursive alternatives:
http://jsperf.com/tco#chart=bar

I have made a module out of this as I intend to use it nodejs
https://github.com/Gozala/js-tail-call

Thanks for feedback and suggestions!

Slightly off-topic - I knew semicolons were mostly optional in JS but I did not know the code looks so much more readable without them! Something to learn for me coming from Java/C/C++:) Great stuff.

@ypocat Yeah I think so too. You might want to check out:
http://aresemicolonsnecessaryinjavascript.com/

Hurray for bad coding styles :P

@Gozala Thanks much for that link Irakli, the few gotchas are good to know.

@jdalton Well, coffee-script is the second most-depended-upon module in npm, but I will not use it because its local variable scoping is total trash (same as Ruby), the function parameter "shims" make for ambiguous APIs (same as Ruby), and besides the better code readability, it doesn't solve any real problems (e.g. async programming with proper error handling), to justify another compilation and indirection layer on top of JS. But seeing Gozala's code, I realized that the main reason why I was looking at CofeeScript was a slightly better readability, which JS without semicolons fully gives me. You could call it broken, but in my book, if there is a feature of the language which comes directly from the spec, and people don't use it despite the fact that it makes the code much more readable, I think it's actually their code that deserves the label "bad coding style", logically speaking.

@ypocat I meant we all prefer a certain code style and others stink :)

@Gozala. Thanks for your sharing. This is a little tricky at the first sight. I've got one question: Is this line active = false at the accumulator() really necessary?

@Gozala Congratulation for the conciseness of the solution.

Along similar lines, but taking the path of "explicit" tail calls, similarly to Syntactic Tail Calls, there is fext.js. It deals with performance and mutual recursion.