Today, I’m going to go over the Fibonacci Series and how we can use a couple of methods to solve the problem. I’ll be going into detail with each solution while breaking down each step. If you’re currently looking for JS algorithms to practice, take a look at my last two blog posts for a few easier algorithms to tackle.
JS: String Reversal, Palindromes, and Anagrams
JS: Integer Reversal and FizzBuzz!
The Fibonacci Sequence
Before we tackle this one, let’s go over what the Fibonacci sequence is. Here is a series of numbers.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,…
The numbers you see above are the first 13 numbers in the sequence. The numbers go on and on but to keep it simple, we’ll keep it at 13 numbers.
If you haven't already figured it out, the next number in the sequence can be found by adding the two numbers before it. The next number in the sequence would be found by adding 89 + 144. With that in mind, the next number would be 233.
If you look at the 7th number in the sequence, 8, the two numbers before that are 5 and 3. 5 +3 = 8. It’s that simple!
The Algorithm
Print out the nth entry of the Fibonacci Series. If we pass in 6 as the argument in our fib function, we would expect our function to return 5. If that doesn’t make sense, take another look at the sequence above. The 6th entry in the sequence is 5.
Solution #1: Iterative Solution
The iterative solution is the easier of the two (in my opinion) and can be solved with afor in just a couple of steps. If we want to return the nth entry of the Fibonacci Series, we’ll have to first create an array that will house our sequence up to the nth entry. We’ll also fill it with the first two entries of the sequence to give ourselves a bit of a start on the sequence. Let’s start coding.
function fib(n) { const seq = [0, 1]}
The next step will involve building a for loop. Since we already have the first two entries of the sequence in our seq array, we can begin our for loop at the 2nd position like so.
function fib(n) { const seq = [0, 1] for(let i = 2; i <= n; i++) { }}
Again, we’re starting our for loop at the 2nd array position because we already have our first two entries in the seq array.
Now, all we have to do is figure out how we can add the two previous entries to come up with the next number in the sequence. We know that the previous two entries added up will equal the next entry so let’s create two variables, a and b that will equal each of the two previous entries.
function fib(n) { const seq = [0, 1] for (let i = 2; i <= n; i++) { const a = result[i - 1] const b = result[i - 2]
}}
For the first run-through of the for loop, we used result[i-1] to grab the 1 in the seq array and result[i-2] to grab the 0. For every subsequent run-through of the loop, a and b will equal the previous two entries of the seq .
Now, all that is left to do in the loop is add these two variables together and push them into the seq array.
function fib(n) { const seq = [0, 1] for (let i = 2; i <= n; i++) { const a = result[i - 1] const b = result[i - 2] result.push(a + b) }}
Our loop is complete and will stop running once the nth entry is reached in the Fibonacci Sequence. Now that we have our nth as the last number in the seq array, all we have to do is return the number.
function fib(n) { const seq = [0, 1] for (let i = 2; i <= n; i++) { const a = result[i - 1] const b = result[i - 2] result.push(a + b) } return seq[n]}
Since all we’ve done here is return the last number in our seq array, we could also write the solution as return seq[seq.length — 1]
And that is it for our iterative solution! This solution is very easy to understand and can be pretty easy to remember. Let’s move on to the next solution.
Solution #2: Recursive Solution
In some cases, you might encounter an interviewer that asks you to solve this problem using a recursive solution. While the solution might be difficult to figure out on your own, once you’ve done it once, you’ll get the hang of it.
Let’s get right into the solution and talk about how and why it works. This format is a bit different than how I usually approach solving algorithms but you’ll understand why I took this approach as opposed to going over the solution step-by-step.
function fib(n) { if (n < 2) {
return n
} return fib(n - 1) + fib(n - 2);}
The first conditional statement exists for one purpose. If the argument to the fib function is 0 or 1, those numbers will be returned right away. If you take another look at the Fibonacci Sequence, the first two numbers are 0 and 1 so the rest needs no explaining. If the n argument is 2 or greater, that is when we enter recursion. To get a better understanding of what happens, let's take a look at the diagram below.
If we call fib(5) , our return statement would be return fib(5 — 1) + fib(5 — 2) which translates to fib(4) + fib(3) . Looking at the graph above, fib(4) would branch out to become fib(3) + fib(2) and this would continue until the bottom is reached and a final value is added up. If this doesn’t make sense yet, take a few moments to study the diagram.
Once we reach the bottom of the diagram, we’ll have instances where were calling fib(1) and fib(0) and if you remember, we automatically return 1 for fib(1) and 0 for fib(0) . If we add up all of the blue squares, we would get 5. Looking at the Fibonacci Sequence again, the 5th number is indeed 5.
Again, this might not make a lot of sense at first but I urge you to study the graph and if recursion doesn't make sense just yet, read this helpful article from Javascript.info .
Conclusion
If you’ve managed to reach the end, please don’t feel discouraged if the recursive solution doesn't make sense. It is one of those solutions that end up being a matter of having seen it before or not. I couldn’t have come up with the solution myself but I’m hoping this post helps with your overall understanding of how we can tackle the Fibonacci Series.
Thanks for reading!
