Solving Fibonacci: Iteration
You might remember Fibonacci’s sequence from when your high school math teacher spent a class talking about cauliflower, but today we are going to revisit Fibonacci (minus the veggies, sorry!) and write the iterative algorithm to solve this very common interview question.
The Problem
The goal of this fibonacci sequence algorithm is to print out the nth entry in the Fibonacci series. If you are unfamiliar, Fibonacci’s sequence is a series of numbers in which each number is the sum of the two preceding numbers.
Before we get started on going over the solution to this problem, I want to let you know that Fibonacci’s sequence was actually the first algorithm I ever solved on my own. So, after you take a look at the problem statement, I definitely suggest trying to solve it on you own first. I imagine you might be surprised at your own ability to come up with at least of these solutions, just like I was.
The Solution
function fib(n) {
let fibSeq = [0,1]
for (let i = 2; i <=n; i++) {
let newNum = fibSeq[i-1] + fibSeq[i-2]
fibSeq.push(newNum)
}
return fibSeq[n]
}I think that the biggest trick to this solution is the realization that you won’t be able to generate the first two numbers in the sequence with an iterative for loop. To solve this problem, as you can see, I just manually inserted the first two numbers, 0 and 1, into my fibSeq array and in doing so was able to effectively use iteration to solve the rest of this problem.
Hopefully, however, the rest of this solution seems pretty straight forward. Basically, what we are doing is using a for loop to iteratively generate the next numbers in the sequence. In our for loop, we take the previous two numbers in our sequence and add them together to make “newNum”. Then, we can push that new number into our series and start again, until we reach the nth number.
Is this solution a good solution?
The iterative solution to this problem aka the one we just wrote, is actually a great and very fast solution to this problem. It has a runtime of O(n) or a linear runtime.
However, if you are familiar at all with this problem, you might be aware that there is another, non-interative solution to the Fibonacci series problem. That solution would be the recursive solution and not only is it more complex to think of and write, it also has a much higher runtime complexity than our iterative solution written above.
That being said, the recursive solution is definitely one to know and understand if you are preparing for technical interviews, so check back in next week to see my explanation of how the other (and much worse) solution to this problem works!
As always, happy coding!
Sources:
