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!
Iterative Solution
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.
Recursive Solution
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
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:
To see how much this solution speeds up the recursion solution, review the tree diagram above again. When look at how many multiple function calls are made, the memoization solution eliminates the need to rec-all the functions. Instead, the hash map build will just return the answer that’s been stored.
Conclusion
According to the Udemy course, it’s best to practice these solutions because coding interviewers may want a different solution that what is initially provided. With me, I was only able to get the iterative solution at the start and had a hard time to get the other solutions. However, once I was able to review this lesson and practice, the recursive solution makes sense as well as the reasons behind why it may not be the best solution due to the number of calls needed to be made. My next thought did go to creating some type of hash map to store values, but I couldn’t think of a way to complete that. Thankfully, the Udemy course went through that with memoization, storing a cache of values to return instead of needing to call the function again since it already did it before.
This lesson was great practice because there will be times where we would need to expand on a solution and think of different ways solve an algorithm. Luckily though, practice makes perfect. Now it’s time to practice on other commonly asked algorithms.
