Fibonacci for newbies!

The last few days I have been studying data structures and algorithms to prepare for potential upcoming interviews as well as taking on leetcode problems. So lets solve the leetcode problem #509 Fibonacci Number!

I want to write this article to help solidify the knowledge I've learned and maybe this will help out another newbie as well.

So what is this Fibonacci that's been mentioned?

The Fibonacci sequence is the integer sequence where the first two terms are 0 and 1. After that, the next term is defined as the sum of the previous two terms. Source

What does this really mean? 🤔

Essentially we take the initial terms 0 and 1, then add those together, then we continue on to the next set of terms which would be 1 and 1, then those are added together to get 2. Then 1, 2 to get 3 and so on. You would continue to add the numbers similarly to get the respective Fibonacci numbers, (check out the banner picture above to see what I mean).
All this being said the terms added together are the Fibonacci numbers so the 10th Fibonacci number is 55 as seen below.

Let's take this simple fib function for example:

const fib = (n) => {
  if(n <= 2) return 1;
  return fib(n - 1) + fib(n - 2);
}
console.log(fib(10));
// 55 is returned in the console

Let's break this down so we can understand what's happening in this fib function.

So in the argument we are expecting an integer of n (Remember in this example, we are calling fib and passing in 10), then we are checking if this integer is greater than or equal to the number 2*.
Else if n IS NOT equal to 2 or less, calculations begin to find the answer.
(*2 because remember the Fibonacci sequence has two terms! 0 and 1 these are the base case so once n is less than 2, the if code block will be triggered and then 1 would be returned)

Let's explain this part! 👩🏻‍💻

The first fib(n - 1) is subtracting 1 from the left term and then fib(n - 2) is subtracting 2 from the right term and then we are adding those together. Subtracting 1 from the left term and 2 from the right term is really because of the Fibonacci sequence definition itself.

Remember that F(1) = 1, and for n greater than or equal to 2, the nth Fibonacci number (F(n)) is defined as the sum of the two previous terms: F(n - 1) + F(n - 2).

Let's visualize the function in action!

Click to view Fibonacci call stack visualization

Hopefully seeing what this looks like helps piece everything together better! Now as you can tell from the visual how big the call stack would be if n was a large number! This would cause the function to take a long time to finish because essentially a lot of the terms are repeated. Knowing this we can tidy up this function and make it operate faster by memoizing the value of n and if it has already been 'shown' we will skip it, saving some time!

In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls to pure functions and returning the cached result when the same inputs occur again.
Memoization

Memoizing Fibonacci!📝

const memoFib = (n, memoize) => {
 memoize = memoize || [0, 1]
 if (n !== undefined) return memoize[n];
 return memoize[n] = memoFib(n - 1, memoize) + memoFib(n - 2, memoize);
}
console.log(memoFib(20));
// console returns 6765

Now let's break down what has changed and why it is faster.
As you can see we added another argument to the function, memoize. Inside the function we initialize memoize telling Javascript this should either be the incoming memoize if it's not undefined other wise memoize will be an array of [0, 1]. This is because we are telling the function these are the base cases so basically we do not want to 'see' these terms again. By excluding these base cases from further computing, the function skips redundant calculations, enhancing its speed.

The next line of code is the most crucial for this optimized function! We are checking if n is defined or not within the memoize array and if it is defined we are going to return n from the array since the calculations are already completed

Lastly, the final line of code calculates the fibonacci value for the current value of n by adding the results of the two recursive calls: memoFib(n - 1, memoize) + memoFib(n - 2, memoize).
The result is stored within the array at the index of n, so when another call appears with the same n, the calculated value can just be grabbed from the array instead of redoing the calculations.

This is how the function can be optimized and shed off some time by not having to do repeated calculations!

Hopefully by now you understand Fibonacci a bit more, I know I do! Try it out for yourself and go and challenge yourself to solve the easy leetcode question! Once you do try to beat your previous runtime! If you're bold try the other difficulty questions! Remember practice the HECK out of what you learn to really lock it into your brain!

Conclusions

I'll admit when I initially began learning about data structures and algorithms I was super intimidated and thought "Wow! I may be in over my head! 😅" I really do get a kick out of pushing myself to do things I didn't think I could do before though!

But of course anything new is scary or overwhelming, (or admittedly a bit of both).

To be completely honest going into such depth of learning about this recursive function and the type of data structure it outputs has taught me a lot and gives me a better grasp on the logic! I'll be writing more as I continue to learn about data structures and algorithms. I honestly feel such a sense of excitement of what else can I learn when it comes to coding! Anyone else feel that way?

Feel free to leave feedback or drop something that helped you learn data structures and algorithms!

Until then let's squash these bugs! Connect with me on my socials found on my personal website!