Fibonacci Algorithm Different Solutions in JavaScript | Code with Beto

Hey there! 👋

If you have a Computer Science background, probably, you have heard about the Fibonacci Number, also known as the Fibonacci Sequence.

At its core, the Fibonacci sequence is a series of numbers that starts with 0 and 1, and each number is the sum of the two previous numbers. The formula looks like this:

Fn = Fn-1 + Fn-2

Even though the Fibonacci algorithm is very famous, many people struggle when trying to find an optimal solution, but that's not you! By the end of this blog post, you will know three methods (recursive, memoization, dynamic) to implement the Fibonacci algorithm.

Recursive Solution

A recursive algorithm calls itself with smaller input variables and returns the result for the current input by carrying out basic operations on the returned value for the smaller input. By using recursive algorithms, certain problems can be solved quite easily.

Here is the recursive implementation:

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

Looks pretty simple, right? Only five lines of code.

Although, the recursive solution is elegant and clean, it's crucial to understand that this is a non optimal solution. In fact, this is the worst solution. Recursive algorithms can be very inefficient. Each recursive call adds a new layer to the stack, which means that if your algorithm recurses to a depth of n, it uses at least O(n) memory.

Now let's dive in at what's happening under the hood when we call our Fibonacci function. Let's say that we want to obtain the 5th Fibonacci. Our recursion tree would look something like this.

What is the run time of this function? Observe that the leaves on the tree are all fib(1) and fib(0). Those signify the base cases. The root node has two children. Each of those has two children. Each of those grandchildren has two children, and so on. If we do this n times, we will have O(2^n) nodes, which gives us a run time of O(2^n).

Like I said before, this solution has a terrible runtime. If we implement this in a computer, we would see that the number of seconds to generate Nth Fibonacci increase exponentially.

Let's try to optimize this.

Memoization Solution

Memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the catch result when the same inputs occur again. If we take a look at the recursion tree from the image above, it's easy to realize that there are lots of identical nodes. For example fib(3) appears twice and fib(2) appears three times. Why should we recompute these from scratch each time? We should just cache those results and use it later.

Here is the memoization implementation:

function fibonacci(n, memoize = { 1: 0, 2: 1 }) {
  if (n in memoize) return memoize[n];
  else memoize[n] = fibonacci(n - 1, memoize) + fibonacci(n - 2, memoize);
  return memoize[n];
}

Not bad, right? We still have five lines of code and a much better run time.

While the first recurse function may take over a minute to generate the 50th Fibonacci number on a typical computer, this memoization solution can generate the 10,000th Fibonacci number in just fractions of millisecond.

Now let's take a look at the recursive tree. The orange circles represent cached calls that returned immediately.

What is the run time of this function? By caching the results of numbers that occur multiple times, we asure that we will never compute the same Fibonacci number more that once. That gives us a run time of O(n).

But wait, there's more!

Dynamic Programming Solution

We can still improve the time and space complexity of this function. Let's think for a second. Because we are caching the results of n Fibonacci we are taking a memory space of O(n), where n is the number of items in our memoize object. If you really think about how this works we are just using the last two cached values to get the next n Fibonacci. Therefore, we can get rid of the memoize object and just store the last two Fibonacci numbers.

Here is the dynamic implementation:

function fibonacci(n) {
  if (n === 1) return 0;
  let a = 0;
  let b = 1;
  for (let i = 2; i < n - 1; i++) {
    let c = a + b;
    a = b;
    b = c;
  }
  return a + b;
}

This function is basically storing the last two fibonacci values into a and b. At each iteration, we get the next value (c = a + b) and then move (b, c = a + b) into (a, b).

This explanation may seem pretty obvious, but understanding the process will make other complicated problem painless.

I hope you enjoy reading this post as much as I enjoyed writing it.

Please consider following me: