Fibonacci Sequence Algorithm

To start the Fibonacci Sequence is a sequence of numbers starting with 0 and 1, then each number after that is derived by adding the two previous numbers. This sequence of numbers is infinite, but here are the first 10 numbers of the sequence for an example of it:

0,1,1,2,3,5,8,13,21,34......

Photo by Ira Mint on Unsplash

From this what we need to solve or what we might be asked in a coding interview to solve is to write a function that gives you back the nth number in the Fibonacci sequence. Most of these algorithm problems you might encounter on a coding interview have been solved a number of ways some more efficiently than others.

For this example, I will write out in JavaScript two ways of solving it the basic iterative solution with a for loop and the recursive solution. First, below is the code for the iterative solution:

function fibonacci(n){
  let fibArray = [0,1]
  for (let i=2; i < n + 1; i++) {
    fibArray.push(fibArray[i-2] + fibArray[i-1])
  }
  return fibArray[n]
}

We begin by creating an array and placing the first two numbers in it. Then using a for loop we add the previous number and the number two numbers before the current point in the array and push that sum to the end of the array. This loop continues to run until the input n+1 is then equal to the i which began at 2. Our return statement then takes from the array we created the nth number. This works and isn’t a bad solution as it Big O time complexity is O(n) as it runs through the for loop.

The next solution using recursion is a good example to see how recursion works or to learn recursion. Below is the code for the recursive solution:

function fibonacci(n) {
  if (n < 2) {
    return n
  }
  return fibonacci(n-1) + fibonacci(n-2)
}

The code for this solution seems short and simple. However, it is not very practical as it has a Big O time complexity of O(2^n) which is bad and not what you’re looking to achieve. As n increases the time complexity grows exponentially because of the exponential increase in function calls. For each number of n greater than 2, we make two more function calls.

The Udemy course The Coding Interview Bootcamp: Algorithms + Data Structures goes through several solutions for this problem.