fib.js

/*
 * nth-fib in both recursive and iterative (dynamic programming)
 *
 * 0, 1, 1, 2, 3, 5, 8, 13, 21
 */

// time: O(2^N) -- derived from branches (2) to the power of it's maximum depth (N); it is EXPONENTIAL
// space: O(N) -- derived from space used on the call-stack, the recursion will go down to N
function fibRecursive(n) {
  if (n <= 1) return n;
  return fibRecursive(n - 1) + fibRecursive(n - 2);
}

// time: O(n) -- derived from doing a single pass from 0 to N; LINEAR (huge huge huge difference)
// space: O(n) -- derived from the space utilized for storing "previous" values (of n-1 and n-2)
function fibIterative(n) {
  const cache = [0, 1];
  // doesn't enter the loop until n is >= 2 (0 and 1 already in cache [skip])
  for (let i = 2; i <= n; i++) {
    cache[i] = cache[i - 1] + cache[i - 2];
  }
  return cache[n];
}

// time: O(n)
// time: O(1) -- we only need to keep the LAST 2 computed values around (cache/memo size of 2)
function fibOptimal(n) {
  const cache = [0, 1];
  for (let i = 2; i <= n; i++) {
    const nMinusOne = cache[1]; // save current n-1 value that's about to be overwritten
    cache[1] = cache[0] + cache[1]; // overwrite current n-1 value with nth-fib
    cache[0] = nMinusOne; // replace n-2 value from saved n-1 value (2 lines up)
  }
  return n === 0 ? cache[0] : cache[1];
}

const testCases = [
  // input, output (expected)
  [0, 0],
  [1, 1],
  [2, 1],
  [3, 2],
  [4, 3],
  [5, 5],
  [6, 8],
  [7, 13],
  [8, 21]
];

const test = ([description, fibFunction, cases]) => {
  console.log(description);
  cases.forEach(c => {
    [n, expected] = c;
    const result = fibFunction(n);
    if (result !== expected) {
      console.log(`N: ${n} | got: ${result} | expected: ${expected}`);
    }
  });
  console.log("\n");
};

[
  ["recursive", fibRecursive, testCases],
  ["iterative (dynamic programming)", fibIterative, testCases],
  ["iterative (dynamic programming) OPTIMAL", fibOptimal, testCases]
].forEach(test);