fibonacci iterative and recursive
123456789101112131415161718192021222324252627282930313233
// Given a number N return the index value of the Fibonacci sequence, where the sequence is:
// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...
// the pattern of the sequence is that each value is the sum of the 2 previous values, that means that for N=5 → 2+3
//For example: fibonacciRecursive(6) should return 8
// O(n)
function fibonacciIterative(n: number) {
let fib = [0, 1];
for (let i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
}
// O(2 ^ n)
function fibonacciRecursive(n: number): number {
if (n < 2) {
return n;
};
return fibonacciRecursive(n - 2) + fibonacciRecursive(n - 1);
}
let val = 6;
console.log('Fibonacci recursive ' + val + ': ' + fibonacciRecursive(val));
console.log('Fibonacci iterative ' + val + ': ' + fibonacciIterative(val));
val = 10;
console.log('Fibonacci recursive ' + val + ': ' + fibonacciRecursive(val));
console.log('Fibonacci iterative ' + val + ': ' + fibonacciIterative(val));
TypeScript
INFO