get-fibonacci.js

//get the nth number in fibonacci sequence, base case is 0 and 1.

//solution 1, easier to understand but it's not good. It has a time complexity of O(2^n).
function fib(num) {
  if (num === 2) return 1;
  if (num === 1) return 0;
  return fib(num - 1) + fib(num - 2);
}
fib(6) //returns 5


//solution 2. Better, uses memoization to stop repeating the same task. It has a time complexity of O(n). Much better than the previous solution.

function fib(num, memo = []) {
  //edge case if (num === 0) return null; 
  if (memo[num] !== undefined) return memo[num];
  if (num === 2) return 1;
  if (num === 1) return 0;
  const result = fib(num - 1) + fib(num - 2);
  memo[num] = result;
  return result;
}
fib(6); //returns 5


//solution 3, Best. It has a time complexity of O(n). It doesn't use recursion and doesn't cause/reach stackoverflow.
function fib(num) {
  if (num <= 2) return 1;
  const fibNums = [0, 0, 1];
  for (let i = 3; i <= num; i++) {
    fibNums[i] = fibNums[i - 1] + fibNums[i - 2];
  }
  return fibNums[num];
}
fib(6) //returns 5