The Fastest and Most Efficient Way to Calculate Fibonacci Series in JavaScript

Neither recursion nor iteration, Binet’s formula takes the cake

Photo by Austris Augusts on Unsplash

What’s Fibonacci?

Fibonacci numbers or Fibonacci sequence is a sequence of numbers that is calculated by adding values of two preceding numbers. It’s also known as the golden ratio and it’s widely found in nature.

We count the sequence starting with index n = 0which has the value of 0and n = 1 is 1.

Thus, the next element (n = 2) is 1(as previous values were 0 + 1). 3rd element (n = 3) is 2 (as 1 + 1), 4th is 3(1 + 2), 5th is 5 (2 + 3) and so on

The formula is defined as

F(n) = F(n-2) + F(n-1) // for n > 2, e.g. F(2) = F(0) + F(1)

The first 21 numbers are:

0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765

Any algorithm should return the same values for identical input. Basically, what we are looking for is to pass the sequence index number (n) and get the corresponding value in return. Examples:

fibonacci(0);  // returns: 0
fibonacci(1);  // returns: 1
fibonacci(2);  // returns: 1
fibonacci(5);  // returns: 5
fibonacci(10); // returns: 55
fibonacci(20); // returns: 6765

Recursive Algorithm

The simplest and easiest algorithm is the recursive algorithm. All recursive algorithms work on the same principle. The function calls itself and passes results from the previous calculation.

function fibonacci(element) {
    if (element === 0) return 0;
    if (element === 1) return 1;
    
    return fibonacci(element - 2) + fibonacci(element - 1);
}

The downside of a recursive algorithm is that it needs to recalculate all previous values each time. Thus, it’s not very effective and time complexity is exponential: O(2^N).

Recursive Algorithm with Memoization

We can drastically speed up our previous algorithm with a technique called memoization. Basically, we will keep values of previous calculations in memory, i.e. we will use additional cache variable to…