JS Algo: Classic Fib — Iterative, Recursive, and Memoize Solutions

For the past month or so, I’ve been focusing on my vanilla JavaScript skills through JavaScript30 (view my progress on my website!). Because of this, I’ve been neglecting on algorithms, so I decided to jump back into it. I’ve been working through my Udemy course with Stephen Grider (which is super awesome and highly recommended) and I was very intrigued by one of the lessons about the Fibonacci sequence. It’s definitely a classic interview question, but upon my first try, I was only able to get one type of solution down. After watching through the tutorial, the other ways to solve make a lot of sense and I wanted to describe what I learned in this blog!

What is the Fibonacci Sequence?

The Fibonacci Sequence is a series of numbers where a number is the addition of the last two numbers, where the first two numbers are 0 and 1. The sequence will populate as follows:

[0, 1, 1, 2, 3, 5, 8, 13, …]

As an expression, it’s written as:

While the number may seem to be use just for brain teasers, it’s been used in branches of advanced mathematics, applications in computer science, statistics, nature, and agile development. Other than that, you’ll most likely come across this during a technical interview.

Now let’s work on the algorithm!

With the iterative solution, you would build the full sequence up through the n-th value using a for-loop. To start off, we can build an array of the sequence with the first two numbers already include since there’s we always know it’ll start with 0 and 1, then build the sequence from there. Then in the for loop, build out the sequence by pushing the sum of the last two values in the array up to the n-th value and then return it! Peep this solution below:

In terms of runtime complexity, the runtime is dependent on the value of n and extends as that increases. Based on this solution, we do have single for-loop included, therefore this solution has a linear runtime.

As with all recursive solutions, there needs to be a point where the function ends. Since we know that the 0-th value will always be 0 and the 1-th value is always 1, then we know that we would return n for anything value less than 2. Outside of that, we would need add the last two values of the sequence. For everything else, we will use recursion to call the function on itself and return the sum of the last two numbers of the sequence. Peep this solution below:

In terms of runtime complexity, we would need to call the function on itself more and more times as the value of n increases. To visualize this, see this diagram from Leetcode for the 5th value of the sequence:

As you can see, the function is called many times in order to get the end case statement where n is less than n. But as n increase, the number of calls to the function would be the same as the n-1 plus more. In short, the runtime complexity exponentially increases.

Memoization means to store the arguments of function call and pair it with the result. So if the function were to be called with the same argument, we can just return the result we got instead of having the call the whole function over again. This method is like building a hash map, but instead using the arguments and return results as key/value pairs. This method still uses recursion, but also uses a helper function to build out and use the hash map. Peep the solution below: