Question: Write a function to calculate the Nth fibonacci number.

There are many possible approaches to this problem. The simplest answer is to do it recursively. This has a O(2^n) time complexity but if you memoize the function, this comes down to O(n).

// Recursive, O(2^n)
const fib = (n) => n < 2 ? n : fib(n-1) + fib(n-2);
}

// Memoize O(n)
// use underscore _.memoize
const fib = _.memoize((n) => n < 2 ? n: fib(n-1) + fib(n-2));

You can do it iteratively going either forwards or backwards.

// Iterative, O(n)
function fib(n) {
  let [a, b] = [0, 1];
  while (n-- > 0) {
    [a, b] = [b, a + b];
  }
  return b;
}

// or
function fib(n) {
  let arr = [0, 1];

  if (n <= 2) return 1;

  for (let i = 2; i <= n; i++) {
    arr[i] = arr[i - 1] + arr[i - 2];
    // arr.push(arr[i-1] + arr[i-2])
  }

  return arr[n];
  // return arr...for list of all values!!!
}

fib(10); // 55

For style points you can use a generator.

// Generator, O(n) when all numbers calculated
function* fib(n) {
  [a, b] = [0, 1];
  while (true) {
    yield a;
    [a, b] = [b, a + b]
  }
}

// instantiate the fib generator
const fib_gen = fib();

// get first 10 numbers
for (let i = 0; i < 10; i++) {
  console.log(fib_gen.next().value);
}

Coolest of all, you can use tail call optimization which has been added to JavaScript in ES6. In tail-call optimization, you are able to make function calls without growing the call stack because you simple return the value from the called function.

// Tail Call optimization
function fib(n, a=1, b=0) {
  if (n === 0) {
    return b;
  } else {
    return fib(n-1, b, a+b);
  }
}

// ES6 Tail Call optimization
const fib = (n, a = 1, b = 0) => (n === 0) ? b : fib(n - 1, a + b, a);

fib(10); // 55

For a fantastic series on memoization and its use with the Fibonacci sequence, see this series by taylodl.



Want to improve your JavaScript? I have a list of recommended JavaScript books.