One Pager Cheat Sheet
- Implement a function
fibonacci(n)
which returns the number in theFibonacci
sequence wheren <= 40
, with a time and space complexity ofO(n)
. - The Fibonacci sequence can be effectively generated using Recursion in order to efficiently calculate each successive number from the sum of the two prior.
- By storing intermediate results and using a
recursive
approach, the Fibonacci Sequence can be calculated with a complexity of `O()$. - We can memo-ize (store) previous function calls and their results by using the
memoize
function, which uses ahash map
as astorage
. - To improve performance in recurring algorithms, use
memoize
towrap
thefibonacci
function.
This is our final solution.
To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.
xxxxxxxxxx
38
}
var assert = require('assert');
​
/*
* @param {number} n The Fibonacci number to get.
* @returns {number} The nth Fibonacci number
*/
​
function fibonacci(num) {
if (num < 0) throw 'num must be >= 0';
if (num === 0) return 0;
if (num === 1) return 1;
​
return fibonacci(num - 1) + fibonacci(num - 2);
}
​
try {
assert.equal(fibonacci(1), 1);
​
console.log('PASSED: ' + '`fibonacci(1)` should return `1`');
} catch (err) {
console.log(err);
}
​
try {
assert.equal(fibonacci(17), 1597);
​
console.log('PASSED: ' + '`fibonacci(17)` should return `1597`');
} catch (err) {
console.log(err);
}
​
try {
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
Got more time? Let's keep going.
If you had any problems with this tutorial, check out the main forum thread here.