Pretty tail-call recursion for JavaScript.

gistfile1.txt

// This was created as an answer for this JSMentors discussion: https://groups.google.com/d/topic/jsmentors/rG9KDmy7Z6A/discussion

/**
 * Call this on a function to get a version that will do infinite tail-call recursion.
 * The function that is passed in should take a function as its first argument.
 * Instead of calling itself to recurse, the first argument should be called (when in tail position).
 * 
 * @example
 *   var factorial = tailCallable(function(recurse, n, total) {
 *     total = total || 1;
 *     return n <= 1 ? total : recurse(n - 1, n * total);
 *   });
 *   factorial(5);
 *   factorial(1000000); // <- this would normally hit the stack limit, but doesn't now
 */
var tailCallable = function(func) {
  // This stores the arguments for the function tail-position
  var recurseArgs = null;
  // `recurse` will be passed to `func` as its first argument. Calling it simply stores 
  // arguments for calling later (once we've left func's stack frame).
  var recurse = function() {
    recurseArgs = Array.prototype.slice.call(arguments);
  };

  // Send back a tail-callable function 
  return function() {
    // Pull out the arguments we were called with
    recurse.apply(this, arguments);
    while (recurseArgs) {
      // store the arguments to be used in a recursive, tail-position call...
      var args = recurseArgs;
      // ...and clear them since we're using their presence above to determine whether to keep "recursing"
      recurseArgs = null;
      // actually call the function!
      returnValue = func.apply(this, [recurse].concat(args));
    }
    return returnValue;
  };
};


// EXAMPLES!

// Factorial:
var factorial = tailCallable(function(recurse, n, total) {
  total = total || 1;
  return n <= 1 ? total : recurse(n - 1, n * total);
});

// Fibonacci Numbers:
// Based on an implementation by Michael Haufe here: https://groups.google.com/d/topic/jsmentors/rG9KDmy7Z6A/discussion
var fibonacci = function(n) {
  var f = tailCallable(function(recurse, n0, n1, step) {
    return step == n ? n1 : recurse(n1, n0 + n1, step + 1);
  });
  return f(0, 1, 1);
};