fibo.js

/* DEFINITION

f(0) = f(1) = 1
f(n) = f(n - 1) + f(n - 2)

f(0) = 1
f(1) = 1
f(2) = 1 + 1 = 2
f(3) = 1 + 2 = 3
f(4) = 2 + 3 = 5
f(5) = 3 + 5 = 8

n    = 0 1 2 3 4 5 6  7  8  9
f(n) = 1 1 2 3 5 8 13 21 34 55
*/

// ALGORITHME

// Version recursive

const fibo_rec = function(n) {
	if (n < 2) {
		return 1;
	} else {
		return fibo_rec(n - 1) + fibo_rec(n - 2);
	}
}

// Version recursive + memoisation

let T = [];

const fibo_mem = function(n) {
	if (!T[n]) {
		if (n < 2) {
			T[n] = 1;
		} else {
			T[n] = fibo_mem(n - 1) + fibo_mem(n - 2);
		}
	}
	return T[n];
}

// Version iterative

const fibo_iter = function(n) {
	let T = [1, 1];
	for (let i = 1; i < n; ++i) {
		let tmp = T[0] + T[1];
		T[0] = T[1];
		T[1] = tmp;
	}
	return T[1];
}

// TESTS

for (let i = 0; i <= 1000; ++i) {
	console.log(`fibonacci(${i}) = ${fibo_iter(i)}`);
}