michaelp0730
1/19/2015 - 6:22 PM

Fibonacci Sequence

The Fibonacci sequence is one of the most famous formulas in mathematics.

Each number in the sequence is the sum of the two numbers that precede it. So, the sequence goes: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on. The mathematical equation describing it is Xn+2= Xn+1 + Xn

When counting the results, exclude the first two numbers (0 & 1), then count up from there.

Memoize Fibonacci.js
content_copyfile_download
// Recursive solution
function fibonacciRecursive(num) {
	if (num <= 1) return 1;
    return fibonacciRecursive(num - 1) + fibonacciRecursive(num - 2);
}

// Iterative solution
function fibonacciIterative(num) {
	var a = 1, b = 0, temp;
    while (num >= 0) {
  	    temp = a;
  	    a = a + b;
  	    b = temp;
        num--;
    }
    return b;
}

console.log(fibonacciRecursive(6));
console.log(fibonacciIterative(6));

// Solution using a memoizer
var memoizer = function (memo, fundamental) {
	var shell = function (n) {
		var result = memo[n];
		if (typeof result !== 'number') {
			result = fundamental(shell, n);
			memo[n] = result;
		}
		return result;
	};
	return shell;
};

var fibonacci = memoizer([0, 1], function (shell, n) {
	return shell(n - 1) + shell(n - 2);
});