fibonacci recursive

fibonacciRecursive

// multiple recursion: one than one recursive call per iteration
// time complexity: O(2^n) or exponential time
// space complexity: O(n)
function fibonacci(n) {
  if ((n === 1) | (n === 2)) return 1;
  return fibonacci(n - 1) + fibonacci(n - 2); // multiple calls of fibonacci
}

// better but still slower than iterative
function fibonacciMemoized(n, cache = []) {
  if (n === 0) return 0;
  if (n === 1) return 1;
  if (cache[n]) return cache[n];

  cache[n] = fibonacciMemoized(n - 2, cache) + fibonacciMemoized(n - 1, cache); // multiple calls of fibonacci

  return cache[n];
}