Comparison of recursive, memoized recursive and dynamic programming approaches to calculating the Fibonacci series.

fib-dyna-in-place.js

function fibDynaInPlace(n) {
  let dp = [0, 1];
  for (let i = 2; i <= n; ++i) {
    dp = [dp[1], dp[1] + dp[0]];
  }
  return dp[1];
}

fib-dyna.js

function fibDyna(n) {
  const dp = {
    0: 0,
    1: 1
  };
  for (let i = 2; i <= n; ++i) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

fib-memo-array.js

function fibMemoArray(n) {
  if (n < 2) {
    return n;
  }
  return fibMemoArray.cache[n] = fibMemoArray.cache[n] || fibMemoArray(n - 1) + fibMemoArray(n - 2);
}
fibMemoArray.cache = [];

fib-memo.js

function fibMemo(n) {
  if (n < 2) {
    return n;
  }
  return fibMemo.cache[n] = fibMemo.cache[n] || fibMemo(n - 1) + fibMemo(n - 2);
}
fibMemo.cache = {};

fib.js

function fib(n) {
  if (n < 2) {
    return n;
  }
  return fib(n - 1) + fib(n - 2);
}

test.js

function time() {
  const hrTime = process.hrtime();
  return hrTime[0] * 1000000 + hrTime[1] / 1000;
}

function shuffle() {
  return 0.5 - Math.random();
}

function testFibs(n) {

  const fibs = [
    fibMemo,
    fibMemoArray,
    fibDyna,
    fibDynaInPlace,
  ].sort(shuffle);

  return fibs.map(function(f) {
    const s = time();
    const r = f(n);
    const e = time();
    return {
      name: f.name,
      iterations: n,
      result: r,
      time: e - s
    };
  }).sort((a, b) => a.time - b.time);
}


const MAX_FIB_N = 1476;
const n = MAX_FIB_N;
const results = testFibs(n);
console.log(JSON.stringify(results, 0, 2));