Created
March 28, 2013 17:38
-
-
Save calebds/5265254 to your computer and use it in GitHub Desktop.
Various JavaScript implementations of a generator for the Fibonacci numbers.
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
| // Naive -> fib(30) runs 2692537 times | |
| var fibNaive = function(num) { | |
| if (num === 0) return 0; | |
| if (num === 1) return 1; | |
| return fibNaive(num - 1) + fibNaive(num - 2); | |
| } | |
| // Memoized -> fib(30) runs 59 times | |
| var memo = {}; | |
| var fibMemo = function(num) { | |
| var result; | |
| if (typeof memo[num] !== 'undefined') | |
| return memo[num]; | |
| else if (num === 0) | |
| result = 0; | |
| else | |
| if (num === 1) result = 1; | |
| else | |
| result = fibMemo(num - 1) + fibMemo(num - 2); | |
| memo[num] = result; | |
| return result; | |
| } | |
| // Iterative -> fib(30) iterates 29 times | |
| var fibIter = function(num) { | |
| var prev1 = 1, prev2 = 0; | |
| var current = 0; | |
| for (var n = 2; n <= num; n++) { | |
| current = prev1 + prev2; | |
| prev2 = prev1; | |
| prev1 = current; | |
| } | |
| return current; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment