get nth fibonacci number

How To Get nth Fibonacci Number in JavaScript?

by

If you’re given an integer n, how would you get the nth number of Fibonacci sequence in JavaScript?

I’ll show you 2 ways to do it, a recursive and an iterative solution.

For this case, we’ll assume the first Fibonacci number is 1, since there are cases where the first Fibonacci number is 0. So, the first few Fibonacci sequence would be :

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, and so on

As you can see, the first Fibonacci number would be 1, the 5th would be 5, the 10th would be 55 and so on.

Iterative Solution

function getNthFibonacci(n) {
    if (n <= 1) return n;

    let total = 1;
    let last = 1;
    let temp = 0;

    for (let i = 2; i < n; i++) {
        temp = total;
        total = total + last;
        last = temp;
    }

    return total;
}

In the iterative solution, we :

  • Check if the number is 1 or below. If it is, just simply return n, since the first Fibonacci number is also 1
  • Iterate through n number of times, adding all the numbers along the way.

Time Complexity : O(n)

We iterate n number of times, so there are n number of operations

Space Complexity : O(1)

We only use some variables and adding none along the way.

Recursive Solution

function getNthFibonacci(n) {
    if (n <= 1) return n;
    return getNthFibonacci(n-1) + getNthFibonacci(n-2);
}

In the recursive solution, we :

  • define a base case to tell the program when to stop, in this case we stop the recursion when n is smaller than or equal to 1.
  • define the recursion to keep returning the result.

Time Complexity : O(2n)

Since in the recursion we keep returning the function twice, there are two recursions that keep happening that makes toe algorithm quite inefficient, but this can be improved.

Space Complexity : O(1)

We don’t increase the memory at any point in time.

More Effective Recursive Solution

You probably would like a recursive solution, but not pleased with the O(2n) complexity, right? Well, good news, we can improve it.

We can use memoization to make the code moree efficient, but I will show you how to tweak our recursion.

function getNthFibonacci(n, secondLast = 0, last = 1) {
    if (n == 0) return secondLast;
    if (n == 1) return last;
    return getNthFibonacci(n-1, last, last + secondLast);
}

The biggest difference here is that we only use 1 recursive call instead of 2 like in the previous solution. That tweak alone drastically improves the complexity.

We use 3 parameters instead of 1 in this solution, but we give the last 2 parameters default value so that it is still clean for us when we call the function.

It works pretty much the same, we keep adding the last and second last numbers recursively to get our desired answer.

Time Complexity : O(n)

Space Complexity : O(1)

Summary

That’s how you can get the nth Fibonacci number. There are a variety of methods to choose from, but most people would prefer the recursive solution.

It also serves as a good practice for your DSA (Data Structures & Algorithms) skills.

If you want to learn how to print the Fibonacci sequence up to the nth number, you can check out my other post, How To Print Fibonacci Sequence In JavaScript?

For you who want to brush up your JavaScript skills, whether to deepen or learn form zero, I recommend you try Codecademy. There are tons of JavaScript lessons that you can learn in a structured and interactive way. You can learn from the most basic materials to advanced stuffs and even preparing for technical interviews. Go try it now!

If you have a better solution be it code-wise or efficiency-wise, please do comment below!

Check out the rest of my blog for more helpful contents on Data Structures and Algorithms in JavaScript!

See you next post!

Leave a Comment