Fibonacci, Recursion & Memoization
For the past year and half I’ve been in an ongoing cycle. I learn something programming related, and I leave with 20 more questions and new concepts to dive into. This recently happened while going over coding interview questions. I was covering the notorious Fibonacci sequence, and had the chance to learn more about memoization and recursion.
For those of you who aren’t familiar with the Fibonacci sequence, it’s a set of numbers where each new number is the sum of the previous two. The start of the sequence is [0, 1, 1, 2, 3, 5, 8, 13, 21,….]. For example, the sum of 0 & 1 is 1, then the sum of 1 & 1 is 2, 2 & 2 = 3, etc. From what I’ve learned, this is a popular topic that comes up in coding interviews. The task is to “Write a function to return n element in the Fibonacci sequence”. Instead of just solving it, I wanted to dive into all the aspects of the algorithm. In the process I learned about three different solutions to the algorithm, an iterative solution(Linear runtime), recursive solution (Exponential runtime) and a recursive, using memoization solution (Linear runtime).
The iterative solution is probably the one that comes to mind first, so here it is.
In this example, we first take in the argument which is the index of the sequence you want to be returned. Then, since we know the first two numbers of the sequence are 0 and 1, we start by placing these two numbers in an array, we’ll call ‘result’. This is our starting point. Next, we create a simple for loop to perform the addition, and append the result to the array, until we reach the value of our number that is our argument. We can start our loop at the index of 2, since we know we already have the first two numbers, 0 and 1 in our array. In order to keep track of our two numbers to be added, we can create variables. One variable, ‘a’ is the number before our current position and the other, ‘b’ is two numbers before our current position. On the first iteration this would result in ‘a’ equalling 1 and ‘b’ equalling 0(the only two numbers we have). Now that we have these numbers, we can add them together and push the result into our array. So now our results array would be [0, 1, 1]. Since we’re in a loop this will continue on until we finally reach our desired number, after we finish looping, we’ll output our results array at the index of the argument.
Next we’ll discuss the recursive solution. Recursion is simply just a function that continues to call itself until a desired outcome, known as the break case. One big caveat of recursion is you must always specify the break case. If you don’t, you’ll be trapped in an infinite loop and your browser will likely timeout once the call stack overflows. Below is a basic recursive solution.
In this solution we start the same, passing in the index we want returned as an argument. To start we determine our break case to be when ‘n’ is less than 2. When we hit this point we will just return ‘n’ and stop calling the function. So for simplicity sake we’ll walk through an example with a low number, fib(3). Since 3 is greater than two, the latter part of our if statement will return. In this example, we will call fib(2) + fib(1). Since fib of 2 isn’t less than 2, it’ll hit the bottom part of our if statement as well. This will result in a call of fib(1) + fib(0). Fib of 0 will always return ‘n’ which is 0, since 0 is less than 2. Fib of 1 will check if the value is greater than 2 as well, and since it’s not it’ll do the same and return ‘n’ as well, which is 1.
Therefore after calling our function 5 times total, we get an answer of 2. This is a result of calling fib(3), giving us fib(2) + fib(1). This then calls fib(1) + fib(0) + fib(1). Once this statement resolves our final equation is 1 + 0 + 1, which gives us 2 . In just this short code block we were able to call the function 5 times, which demonstrates why recursion is so powerful. However the time complexity isn’t always the best. After experimenting with this function, I found that at about n = 40 my browser stopped returning results since it was calling the function way too many times. This issue brings us to our final solution, which in my opinion is the best, recursion using memoization.
Memoization is basically what it sounds like, memorization. It is a technique used to optimize the run time of an equation. It does this by keeping function results in a cache object. This means if we’ve already performed fib(2), we don’t need to run it again. We’ll have an object that remembers the output of this function, and simply return it to us.
The fib function we’ve created stays the same, we don’t need to change anything. We’ll just build an additional function that we can utilize called memoize. This function takes in a callback as an argument, allowing us to pass a function to it to convert it to a super function. In this memoize function block, we start by declaring our cache object, which will store all of our outputs. We use an object to store our results since it is known for having a really fast access time complexity (Best case: O(1), Worst case: O(n)). Now that we have a place to store all of our results, we can return a function that takes in the arguments that are passed into our fib function. Therefore every time we call our fib function we check our cache object to see if we’ve ran it before with this value. If we have then it’ll simply return the stored value from our object, eliminating the need to recompute the function. If this is the first time our cache has seen this argument, it’ll compute our fib function, return the result and store it in the object for us to access immediately the next time we see that argument. Finally in order for this to work, we have to redeclare our fib function to be equal to the memoize function with our original fib function passed in as the callback argument.
Overall, learning about these three solutions really helped better my understanding of these popular programming concepts. I have a favorite, but still feel it was very beneficial to gain a deeper understanding by going over multiple solutions and how they can be applied elsewhere.
Happy coding!
