If you’re familiar with the material I write on my blog, you’ll probably be confused at why I’m making such a post. Anyone who has been a part of a Computer Science program at a university will probably have dabbled with Fibonacci in their first semester of school. However, many Computer Science graduates don’t realize that this is a common job interview question regardless of the company or job level that you’re applying for. Whether you’re applying for a new graduate position or a senior level position, there is a good chance you’re going to be screened with a question on this topic.

With that said, I think this can be a refresher to anyone going through the interview process for a programming or software engineering position.

There are number of different languages you can accomplish this task with. The interviewer may even ask for a pseudo-code alternative rather than language specific. In this article, I’m choosing to use JavaScript because of how common it has become in modern development.

If you’re unfamiliar with the Fibonacci sequence, it can be defined by the following:

Fibonacci via Wikipedia

By definition, the first two numbers in the Fibonacci sequence are either 1 and 1, or 0 and 1, depending on the chosen starting point of the sequence, and each subsequent number is the sum of the previous two.

An example of the sequence can be seen as follows:

There are a few ways you can accomplish finding these numbers, one being with a loop, and one with recursion. At this point, I’m going to assume that you’re already familiar with JavaScript and how to write a class or function.

The first method we’re going to look at is by looping since it is often easier for people to wrap their head around.

1 2 3 4 5 6 7 8 9 |
var looping = function(n) { var a = 0, b = 1, f = 1; for(var i = 2; i <= n; i++) { f = a + b; a = b; b = f; } return f; }; |

We know that Fibonacci number is the sum of the previous two sequence numbers which is why we are starting our loop at index two, which is really the third value since our index starts at zero. The first two numbers in our sequence are zero and one. The goal is to find the Fibonacci number at a certain sequence index, which in this example is fifteen.

Every loop iteration we are summing the previous two sequence values, then pushing our values up in a sense. By this I mean that `a`

is dropped off and replaced with `b`

and `b`

is replaced with the current index value of the sequence, being our new sum. When our loop has reached our desired fifteen index, we can return whatever the new sum value is.

Now let’s take a look at the recursive version of this.

1 2 3 4 5 6 7 |
var recursive = function(n) { if(n <= 2) { return 1; } else { return this.recursive(n - 1) + this.recursive(n - 2); } }; |

Recursion can be a little tricky to wrap your head around. In the above code, we are going to plan on receiving the sequence value at index five because anything larger is going to be rough for me to type out. You can break this down like the following:

recursive(4) + recursive(3)

(recursive(3) + recursive(2)) + (recursive(2) + recursive(1))

((recursive(2) + recursive(1)) + 1) + (1 + 1)

((1 + 1) + 1) + (1 + 1)

5

You can see above that on every line it is one further iteration through the recursive process. Based on our function logic, as soon as `n <= 2`

then we just return a value of one. At the furthest breakdown, our sum turns into five which is the Fibonacci number at index five.

### Conclusion

Know how to do this task. It is a good interview question because it demonstrates your understanding of recursion and looping as well as your thought process in choosing between the two.

A video version of this article can be seen below.