Fibonacci Sequence — JavaScript, Recursion & Memoization
What in world is the Fibonacci Sequence? Let’s break it down first — what is a sequence and a series. A series in math is the sum of a list of numbers that are creating some pattern or following some rule. This then becomes classified as a sequence, when that set of numbers is following some pattern.
The Fibonacci Sequence is a series of numbers, in which each number is called a fibonacci number. In this sequence the fib number is the sum of the previous two numbers before it. See the example below:
Now that we have a clue what the Fibonacci Sequence is, let’s do some recursive problem solving.
PROBLEM: Write a function ‘fib(n)’ that takes in a number as an argument. The function should return the n-th number of the Fibonacci Sequence. In our case, let’s do the 8th number.
We want the 8th number of the sequence — how do you go about this? Let’s draw it out:
Can you recognize the pattern that it’s following? This patter will eventually end and hit its base case. Remember here that these numbers counting down is n, not the actual numbers in the sequence. Let’s try this function below:
Let’s take a look at the first line of the function:
if (n≤2) return 1; - This is used because the first two numbers of the sequence (not including 0) are 1's.
Now let’s take a look at the second part:
return fib(n-1) + fib(n-2); - adding the sum of the number previous to n and the number previous to that number.
Type this into your console and test out the function.
console.log(fib(6)); //8 - Great this works
console.log(fib(7)); //13 - Great this works as well
console.log(fib(8)); //21 - Great this works, did we solve it?What happens when you try out:
console.log(fib(50));
// oh no it's like it's taking forever! What's happening?this is JS... remember the callstack and that JS is single threaded!
Remember this is JavaScript — a single threaded program. One word will let you realize what’s happening, callstack. If we take into consideration the time and space complexity classes, we realize that the time complexity is what’s taking so long => O(2^n) time is the issue. In other words this takes too long in the callstack. It’s saying:
fib(50) ≈ 2^50 steps
answer: 1.12e + 15 // This is a big number!Obviously it’s taking so long because this is a large number. So we found the problem…How can we fix our function? Let’s do some memoization. What is memoization?
Memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again. So in other words, we are going to be storing previous results and then we don’t have to calculate them again.
Step one to converting our function — let’s go back to our node tree, can you see the repetitive nodes throughout?
Okay, great you see the pattern and the sub nodes in the tree. Now can you imagine the tree starting with 50 and how many repetitive sub nodes there would be?! No wonder it takes forever to compute the answer. Let’s add so more logic to involve the memoization in our function.
Let’s think in JavaScript. What in JS is fast acting? In this case we are going to use a JavaScript Object. The keys will be an argument and the value will be the return value.
const fib = (n, memo={}) => {
....
}What the memo object does here is, if you don’t pass in a second argument, by default it will create a “memo” JS Object.
Next, we will add another conditional that will check inside memo if (n) exist, and if it does, return that.
if (n in memo) return memo[n];After, we need to write out: If not in memo, calculate it and then store in the memo object.
memo[n] = fib(n-1) + fib(n-2)Then let’s return memo:
return memo[n];Great, it’s coming together! Wait, seems like we are missing something. Let’s take a look at this again:
const fib = (n, memo={}) => {
if (n in memo) return memo[n];
if (n ≤ 2) return 1;
memo[n] = fib(n-1) + fib(n-2) //what's missing here?
return memo[n];
};We need to make sure the memo object is being used — pass by reference. Reference memo in the code where you are summing up the numbers. Okay so now it should look like this:
Congrats, you’ve now used memoization in this function to speed up the results! Test it out — type in console.log(fib(50)); in your console and look at what YOU did! You will come to realize by using memoization to solve this, you scaled back the amount of recursive calls you were doing from the original function.
Let’s bring this lesson home — think back to the diagram of the node tree. What does our final function look like now since we are storing the previous nodes in our memo object? In the diagram below you can see that we really scaled down the tree or the time complexity overall, meaning it’s a lot faster now.
If you stuck around this long and read — thank you! I’m glad I could teach someone, something that I learned today for fun! Without struggle, there is no progress — keep learning!
❤️XOXO — Nicoll
