Two ways to solve Fibonacci

A very common question that you may come across during a coding interview is to find the Fibonacci sequence with a given number. The Fibonacci sequence is a set of numbers that starts with a one or a zero, followed by a one, and proceeds based on the rule that each number (called a Fibonacci number) is equal to the sum of the preceding two numbers. If the Fibonacci sequence is denoted F (n), where n is the first term in the sequence, the following equation obtains for n = 0, where the first two terms are defined as 0 and 1 by convention:

F (0) = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 …

So during the interview, you will be asked:

Given a number N return the index value of the Fibonacci sequence, where the sequence is:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

After a quick look, you can easily notice that the pattern of the sequence is that each value is the sum of the 2 previous values, which means that for N=5 → 2+3 or in maths:
F(n) = F(n-1) + F(n-2)

The easiest way to accomplish this is with a simple loop:

let fibonacci = (num) => {
    let a = 1;
    let b = 0;
    let temp;

    while ( num >= 0) {
        temp = a;
        a = a + b;
        b = temp;
        num--
    }
    return b;
}

With this solution, we calculate the next number by adding the current number to the old number. And this gives you an O(n) time complexity. But there is a faster approach to the problem. And that approach is called recursion.

let fibonacci = (num) => {
  if (num <= 1) return 1;
  return fibonacci(num - 1) + fibonacci(num - 2);
}

With the recursive function, we go to an O(2^n) time complexity. So we have increased the complexity exponentially. But we are able to solve the question in only 3 lines code.