Created
September 8, 2011 00:08
-
-
Save Artanis/1202231 to your computer and use it in GitHub Desktop.
Memoized, naïve, recursive Fibonacci function in JavaScript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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