Skip to content

Instantly share code, notes, and snippets.

@erikbern
Last active August 29, 2015 14:18
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save erikbern/ba3456f836ccc9c044e8 to your computer and use it in GitHub Desktop.
Save erikbern/ba3456f836ccc9c044e8 to your computer and use it in GitHub Desktop.
simple javascript task framework to flip recursion inside out
function serializeArgs(args) {
return JSON.stringify(args);
}
function unroll(f) {
if (f._cache == undefined)
f._cache = {};
var f_new = function() {
var key = serializeArgs(arguments);
if (f._cache[key] != undefined)
return f._cache[key];
else
throw f_new.task.apply(null, arguments);
}
f_new.task = function() {
var task = function() {
var task = arguments.callee; // same
return runTasks([task]);
}
var args = arguments;
task.run = function() {
var result = f.apply(null, args);
var key = serializeArgs(args);
f._cache[key] = result;
return result;
}
return task;
}
return f_new;
}
function runTasks(tasks) {
while (tasks.length > 0) {
var nextTask = tasks.pop();
try {
// We're running this synchronously, but it could also be async
var result = nextTask.run();
} catch(anotherTask) {
tasks.push(nextTask);
tasks.push(anotherTask);
}
}
return result;
}
var fib = unroll(function(x) {
return x > 1 ? fib(x-1) + fib(x-2) : x;
});
var factorial = unroll(function(x) {
return x > 0 ? x * factorial(x-1) : 1;
});
var nChooseK = unroll(function(n, k) {
return factorial(n) / factorial(k) / factorial(n - k);
});
// Mutual recursion
var isOdd = unroll(function(n) { return n == 0 ? false : !isEven(n-1); });
var isEven = unroll(function(n) { return n == 0 ? true: !isOdd(n-1); });
var t1 = fib.task(43);
var t2 = factorial.task(10);
var t3 = nChooseK.task(12, 7);
var t4 = isEven.task(39);
console.log(t1());
console.log(t2());
console.log(t3());
console.log(t4());
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment