Nth Fibonacci Number

Fibonacci Numbers represent a series of numbers where the nth number is the sum of the previous two elements starting from 0 and 1 as the first two elements. Since ancient times mathematicians around the world have mentioned this series in their work. Whether it is the spiral of a spider web or the arrangement of celestial bodies, hints of the Fibonacci Series can be found everywhere.

In programming, there are many ways to find nth number of the Fibonacci Series and in this article, we will go through some of the cool ones. Mainly

1. Iterative Method
2. Recursive Method
3. Memoized Recursive Method
4. Matrix Multiplication Method
5. Matrix Exponentiation Method
6. Formula for Nth Fibonacci Number

Iterative Method

The simplest approach to find the Nth Fibonacci Number would be to run a loop from 0 to n and keep track of the last and the second last numbers as we can obtain the next element in the series by adding the last two elements.

Following is an implementation of this approach in JavaScript:

function fibonacci(n) {
  if (n === 0 || n === 1) return n;    // handling edge cases
  let prevNum = 0;    
  let currNum = 1;
  for (let i = 0; i <= n - 2; i++) {
    let temp = prevNum;    
    prevNum = currNum;
    currNum = currNum + temp;
    //  OR
    // currNum = currNum + prevNum;
    // prevNum = currNum - prevNum;
    // OR
    // [prevNum, currNum] = [currNum, currNum + prevNum]
  }
  return currNum;
}

Time Complexity: O(n)

Space Complexity: O(1)

Recursive Method

We can find the Nth Fibonacci Number by recursively adding the last two numbers in series. Recursion is used to break down the code into smaller and repetitive problems, making the code easier to understand. This is also the reason why recursion is emphasized by Functional Programming.

Let's solve this recursive problem step by step. The first step would be to identify the base cases. In this scenario, our base cases would be F(0) and F(1). If 0 or 1 is passed as an argument to our function, then we can simply return the number itself as F(0) = 0 and F(1) = 1. Now the second step is to write a recursive statement. We know that F(n) = F(n-1) + F(n-2), so for any F(n) function call we would return F(n-1) + F(n-2) as the recursive statement.

Let's see the code before moving forward,

function fibonacci(n) {
  if (n === 0 || n === 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}
OR
// function fibonacci(n){
//   return n === 0 || n === 1 ? n : fibonacci(n - 1) + fibonacci(n - 2);
// }

Time Complexity: O(2^n)

Space Complexity: O(logn)

Calling fibonacci(5) would generate the following call stack:

And the corresponding return values would be:

We can improve on the time complexity of this approach by using the memoization technique.

Memoization Method

It is an improvement on the previous method. As you might have noticed in the recursion call stack some of the function calls were made more than once. For Example, the function call F(3) is made twice which means that F(3) is calculated at two separate occasions.

To prevent these redundant calls, we can store their return values in our code. This process of storing return values is called memoization and it is a cornerstone of Dynamic Programming.

Memoized code is as follows:

function fibonacci(n, memo = {}) {   
  // initialize memo as empty object
  if (n in memo) return memo[n];   
  // if key 'n' exists in the memo, then return its value
  if (n === 0 || n === 1) return n;
  // store return values in memo object and pass it down to function calls 
  return (memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo));    
  // OR
  // return n === memo
  //   ? memo[n]
  //   : n === 0 || n === 1
  //   ? n
  //   : (memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo));
}

Time Complexity: O(n)

Space Complexity: O(n)

By maintaining a memo object we are able to bring down the time complexity to O(n). Here is the call stack and memo object for the above code:

Matrix Multiplication Method

Let's start by establishing the equation we will be using in this method.

Here is a YouTube video deriving this equation.

From the above equation, it is clear that if we multiply the matrix [[1, 1], [1, 0]], n-1 times then the element at index [0][0] will be the nth Fibonacci number. Check this code:

// returns product of two 2x2 square matrices
function matrixMultiply(a, b) {
  const len = a.length;    
  let res = [
    [0, 0],
    [0, 0]
  ];
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len; j++) {
      for (let k = 0; k < len; k++) {
        res[i][j] += a[i][k] * b[k][j];
      }
    }
  }
  return res;
}
// returns the matrix [[1, 1], [1, 0]] raised to nth power
// note- we will improve this part with exponentiation
function matrixExponent(n) {
  const k = [
    [1, 1],
    [1, 0]
  ];
  let res = k;
  for (let i = 0; i < n; i++) {
    res = matrixMultiply(res, k);
  }
  return res;
}
function fibonacci(n) {
  if (n === 0 || n === 1) return 1;
  let res = matrixExponent(n - 1);
  return res[0][0];    // [0][0] index is our answer
}

Time Complexity: O(n)

Space Complexity: O(1)

Currently, our code finds power of the matrix in O(n) time, we will improve it in the next section.

Matrix Exponentiation Method

Our target is to find the power of a matrix under O(logn) time. This can be achieved using matrix exponentiation. I would recommend you learn binary exponentiation before going through this section.

Let's jump into the code first!

function matrixMultiply(a, b) {
  const len = a.length;
  let res = [
    [0, 0],
    [0, 0]
  ];
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len; j++) {
      for (let k = 0; k < len; k++) {
        res[i][j] += a[i][k] * b[k][j];
      }
    }
  }
  return res;
}
// finds nth power of matrix under logn time
function matrixExponent(n) {
  if (n === 0) {
    return [
      [1, 0],
      [0, 1]
    ];
  }
  const k = [
    [1, 1],
    [1, 0]
  ];
  if (n === 1) return k;
  let temp = matrixExponent(Math.floor(n / 2));
  let res = matrixMultiply(temp, temp);
  if (n % 2 === 1) res = matrixMultiply(res, k);
  return res;
}
function fibonacci(n) {
  if (n === 0 || n === 1) return n;
  let res = matrixExponent(n - 1);
  return res[0][0];
}

Time Complexity: O(logn)

Space Complexity: O(logn)

Matrix exponentiation is easy to understand if you compare it with corresponding binary exponentiation. Note that in this case the value of the matrix was constant, so it wasn't passed as an argument.

Now that we have gone through all sorts of implementations, let's check out the direct formula to find the nth Fibonacci number.

Formula for Nth Fibonacci Number

We can find the nth Fibonacci number directly using the following formula:

Here is the code for this method:

function fibonacci(n) {
  const phi = (1 + Math.sqrt(5)) / 2;    
  return Math.round(Math.pow(phi, n) / Math.sqrt(5));
}

Time Complexity: O(logn)

Space Complexity: O(1)

Note- This formula involves working with fractional numbers, which is something coding languages are not very good at (try executing 0.1 + 0.2 in your console).

Congratulations! you have made it to the end of this article. Do let me know what was your favorite approach in the comments below.