Print out the n-th entry in the Fibonacci series. The Fibonacci series is an ordering of numbers where each number is the sum of the preceding two.

fibonacci.js

// Iterative Fib (Linear runtime)
function fibItr(n) {
	const result = [0, 1];
	
	for (let i = 2; i <= n; i++) {
		const a = result[n - 1];
		const b = result[n - 2];
		
		result.push(a + b);
	}
	
	return result[result.length - 1];
}


// Recursive Fib (Quadratic runtime)
function fib(n) {
	if (n < 2) {
		return n;
	}
	
	return fib(n - 1) + fib(n - 2);
}

// Memoized Fib
function memoize(fn) {
	const cache = {};
	
	return function(...args) {
		if (cache[args]) {
			return cache[args];
		}
		
		const result = fn.apply(this, args);
		cache[args] = result;
		
		return result;
	}
}

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

const fib = memoize(slowFib);