Fibonacci

Tyler Hueter
Nov 1 · 4 min read
The Fibonacci sequence is related to the Golden Ration and seen all over the place in nature. Image from ScienceFriday

We are back to look at yet another very common coding interview challenge…the Fibonacci Challenge. First we need to know what the Fibonacci sequence is. Wikipedia defines it as:

…the Fibonacci numbers, commonly denoted Fn form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F[0] = 0 , F[1] = 1

and

F[n] = F[n-1]+F[n-2]

I would highly suggest reading up on Fibonacci numbers and how they relate to the Golden Ratio. Very cool stuff and not just for math geeks!

Back to the issue at hand. The Fibonacci sequence looks like this: 0,1,1,2,3,5,8,13,21,34,55,89,144 and so on. The challenge is generally worded like:

Create a function that will take in a number and calculate the Fibonacci Sequence then return the value that corresponds with the position matching the given number.

As before, we will go over two different solutions and briefly discuss why one may be more appropriate than the other. These two solutions are not the only two out there and you should challenge yourself to come up with some others. For the first solution we are going to take an iterative approach. Let’s take a look at the code:

The first step was to define an array for our results. A Fibonacci sequence will usually begin with the same two numbers 0 and 1. In some cases the zero will be left off, but for our purposes we are going to keep it in there. Since we know the first two numbers of the sequence we can initialize the array with them. Next, we are going to use a for loop to iterate up to the position the function takes in as an argument. We begin the loop counting up from 2 because we already have the first two positions. Then we set our variables to the two values proceeding the current iteration, and then push the sum of those to numbers into our array. Once we have iterated up to the position indicated by the number the function took in, the function returns the value of that position in our array.

This is a simple and effective solution though not very fancy. Maybe you would like to get a little more complex. Next, we will go over a solution using recursion. This is the process of a function directly calling on itself to derive a solution. This can be tricky because you can make a mistake in your code and create an infinite loop…which is a problem. Let’s take a look at the code and see how to avoid that.

The first thing we do in this function is establish our base case, which is the circumstances in which the function will break out of the recursive loop. So as the function calls back on itself decreasing the number passed in as an argument it will break out of that cycle when that number is less than two. Then it will return the sum of all the smallest parts of that tree. Here is a diagram that will help explain.

So I am not exactly an artist.

As the function calls itself, the number passed in decreases. Then that function call, calls itself and so on until the number passed in hits our base case then it quits the cycle and adds up the values of the final calls. In this case the sum is 8, which is the value of the 6th position in the Fibonacci sequence: [0,1,1,2,3,5,8,13].

Does the recursive part of our function look familiar? Scroll back up to the definition from Wikipedia and see that it includes F[n] = F[n-1]+F[n-2]. This might lead you to think that the recursive solution is the best choice…not so fast(literally!). Your interviewer may want you to also consider time complexity aka Big O notation. Big O notation is a way of measuring the rate at which the runtime of a function will grow. It is a much bigger topic than we will cover here but you can check out these links for more info: 1, 2, and 3. Let’s take another look at those solutions and apply Big O to see the big difference between them.

The first solution that uses a for loop to solve the challenge has a linear growth rate when getting the Big O value for the function. This solution has a notation of O(n), which means that the rate the runtime will increase is determined by the size of n. The second solution’s notation is O[2^n] which shows an exponential growth rate. At the end of the day, this all means that the second solution with take vastly more time to complete as n grows than the first solution. I would suggest that fancy isn’t better in this case and to go with the first solution.

Again, these two solutions are not the only answers to this challenge. Try to find some others for yourself. Good luck out there!

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade