-
-
Save Prinzhorn/1258622 to your computer and use it in GitHub Desktop.
Fibonacci with dynamic programming
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
| /** | |
| @param n calculate fibonacci number of n | |
| */ | |
| function f(a){ | |
| return a < 2 ? //Simple case for first two fibonacci numbers | |
| a : | |
| f[a]||(f[a]=f(a-1)+f(a-2)) //Return value of cache or add value to cache if needed. The function is used as cache. | |
| } |
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
| function f(a){return a<2?a:f[a]||(f[a]=f(a-1)+f(a-2))} |
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
| DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE | |
| Version 2, December 2004 | |
| Copyright (C) 2011 YOUR_NAME_HERE <YOUR_URL_HERE> | |
| Everyone is permitted to copy and distribute verbatim or modified | |
| copies of this license document, and changing it is allowed as long | |
| as the name is changed. | |
| DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE | |
| TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION | |
| 0. You just DO WHAT THE FUCK YOU WANT TO. |
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
| { | |
| "name": "fastRecursiveFibonacciWithDynamicProgramming", | |
| "description": "A recursive but fast implementation of Fibonacci using dynamic programming.", | |
| "keywords": [ | |
| "fibonacci", | |
| "recursive", | |
| "fast", | |
| "dynamic", | |
| "programming" | |
| ] | |
| } |
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
| <!DOCTYPE html> | |
| <title>Fast recursive Fibonacci</title> | |
| <div>Expected value: <b>190392490709135</b></div> | |
| <div>Actual value: <b id="ret"></b></div> | |
| <script> | |
| // write a small example that shows off the API for your example | |
| // and tests it in one fell swoop. | |
| var myFunction = function f(a){return a<2?a:f[a]||(f[a]=f(a-1)+f(a-2))} | |
| document.getElementById( "ret" ).innerHTML = myFunction(70); | |
| </script> |
But then it's leaking the global scope, which is against rule 3. But I see others doing that.
Em... It wouldn't leak the global scope actually.
For example, the following code will cause "Uncaught ReferenceError: f is not defined",
as Function expressions is not Function declarations.
var a = function f(){};
alert(f);
OK, I see what you did there.
why not use the function as the cache?
function f(a){return f[a]=a<3?1:f[a]||f(a-1)+f(a-2)}
Smart move!
That was indeed a smart move. But it destroyed the case where a is 0. Your code returns 1 for f(0) which is by definition 0.
I committed a tweaked version of yours, which is just two bytes longer.
well, you only need the extra two bytes avoid the unneeded assignment. since it's so cheap, i think it's worth it.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Try to reuse the original function
function f(n,c){return(c=c||[0,1,1])[n]||(c[n]=f(n-1,c)+f(n-2,c))}