One Pager Cheat Sheet

• Implement a function fibonacci(n) which returns the number in the Fibonacci sequence where n <= 40, with a time and space complexity of O(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($2^n$)$.
• We can memo-ize (store) previous function calls and their results by using the memoize function, which uses a hash map as a storage.
• To improve performance in recurring algorithms, use memoize to wrap the fibonacci 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

}

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 {

Great job getting through this. Let's move on.

If you had any problems with this tutorial, check out the main forum thread here.