The Fibonacci Sequence Printed With JavaScript

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:

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 …

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.

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.

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.

Nic Raboy

Nic Raboy is an advocate of modern web and mobile development technologies. He has experience in Java, JavaScript, Golang and a variety of frameworks such as Angular, NativeScript, and Apache Cordova. Nic writes about his development experiences related to making web and mobile development easier to understand.

  • arDeB

    Tnx a lot, great solution.

  • George Portillo

    Also note that this is a very expensive task. If you want to greatly increase the efficiency of the function, make sure to use memoization.

    • Thanks for your input! Can you provide an example or a link to an example of what you’re referring to?

      • Aslam Tajwala

        Memoization is a technique wherein you save results of a computation in a cache and later use that value directly from the cache instead of computing it.

        I wrote you a memoized function here:
        http://jsfiddle.net/atajwala/s44twvup/

        • Great!!

        • Vol7ronForum

          Of course this could be greatly improved:

          • This is an interesting solution. Thanks for sharing!

          • Vol7ronForum

            Welcome, Nic; thanks for the article.

            It isn’t a complete solution as it doesn’t scrub/validate inputs, or work in the negative direction; but it might be the fastest/quickest that works with positive pre-validated integers 😉 but I’ve never used a fib series other than as an academic exercise.

  • Emerson

    Thanks man. Helped a lot.

  • Chris

    For the recursive solution, shouldn’t the base case be return num instead of return 1? For instance fibonacci of 0, should equal 0. However with your implementation it would return 1.

  • Xavier Artot

    The recursion solution is a terrible choise, you call the function 36 000 times, my way:
    var sumFibs = function sumFibs(num) {
    var n = [1, 1];
    while (n[n.length-1] + n[n.length-2] <= num) {
    n.push(n[n.length-1] + n[n.length-2]);
    }
    console.log(n);
    return n
    };

  • Emily Ann

    Where does it state 15 is the desired index? I don’t see that declared or mentioned anywhere in the code!!!!