Skip to content

Instantly share code, notes, and snippets.

@Artanis
Created September 8, 2011 00:08
Show Gist options
  • Save Artanis/1202231 to your computer and use it in GitHub Desktop.
Save Artanis/1202231 to your computer and use it in GitHub Desktop.
Memoized, naïve, recursive Fibonacci function in JavaScript
// Take a function and return a function that caches the results of
// that function.
//
// Setting debug to true will print the logic the caching function uses.
var memoize = function(fn, debug) {
// Caching object, in the form {args : value}
var cache = {};
// Caching function. No explicit args. Any args are fed into the
// memoized function via apply().
return function() {
// Turn arguments object into a real array.
var arguments = [].slice.apply(arguments)
// Generate a string suitable for being a key in an object.
var args = JSON.stringify(arguments);
// Check for previous call.
if(cache[args] !== undefined) {
if(debug === true) {
print("In cache: (" + args + ", " + cache[args] + ")");
}
} else {
// No previous call, call the function.
// Point of interest: apply() doesn't work without 'this',
// which is the global object in this case.
var value = fn.apply(this, arguments);
if(debug === true) {
print("Brand new: (" + args + ", " + value + ")");
}
// Store the result in the cache, using the arguments as
// the key.
cache[args] = value;
}
// Return the pre-calculated value.
return cache[args];
};
};
// Generate fibonacci numbers using naïve recursion.
var fibonacci = function(n) {
return n === undefined ? 0:
n == 0 ? 0:
n == 1 ? 1:
fibonacci(n-1) + fibonacci(n-2);
};
// Replace naïve fibonacci with cachin fibonacci.
// This is the key step: when the fibonacci function goes to call
// itself, it finds this new value.
fibonacci = memoize(fibonacci, true);
// Generate a ton of numbers in crazy short time.
print(fibonacci(100));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment