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.