Fast Recursive Fibonacci

Recursive Fibonacci with better complexity

by kouty79

HTML

<div id="out">
</div>

JavaScript

function fibonacci(n) {
  if (n === 0)
    return [0, 0];
  else if (n === 1)
    return [1, 0];
  else {
    const prev = fibonacci(n - 1);
    return [prev[0] + prev[1], prev[0]];
  }
}

const out = document.querySelector('#out');
const sequenceIndex = 35;

let start = performance.now();
let val = fibonacci(sequenceIndex)[0];
let msg = 'Fibonacci FAST, val: ' + val + ', Time ms: ' + (performance.now() - start);
console.log(msg);
out.innerHTML = msg;

function fibonacciSlow(n) {
  if (n === 0)
    return 0;
  else if (n === 1)
    return 1;
  else {
    return fibonacciSlow(n - 1) + fibonacciSlow(n - 2);
  }
}

start = performance.now();
val = fibonacciSlow(sequenceIndex);
msg = 'Fibonacci SLOW, val: ' + val + ', Time ms: ' + (performance.now() - start);
console.log(msg);
out.innerHTML += '<br>' + msg;