AI solution for JavaScript Coding Question on BFE.dev
86. Generate Fibonacci Number

Solution:

There are multiple ways to implement the fib(n) function. One of the simplest ways is to use recursion.

function fib(n) {
  if (n === 0) return 0;
  if (n === 1) return 1;
  return fib(n-1) + fib(n-2);
}

This function checks the base cases where n is either 0 or 1, and returns their respective values. If n is greater than 1, it calls itself twice with n-1 and n-2, and adds the results to get the n-th Fibonacci number.

The time complexity of this function is O(2^n), because in the worst case scenario, each call generates two new calls, resulting in an exponential growth. The space complexity is also O(n), because the function call stack will have a maximum depth of n.

A more efficient way to generate Fibonacci numbers is to use iteration and store the previous two values.

function fib(n) {
  if (n === 0) return 0;
  if (n === 1) return 1;
  let prev = 0, curr = 1, next;
  for (let i = 2; i <= n; i++) {
    next = prev + curr;
    prev = curr;
    curr = next;
  }
  return curr;
}

This function starts with prev equal to 0 and curr equal to 1, and iterates n-1 times, adding prev and curr to get next, and updating the variables accordingly. The final value of curr is the n-th Fibonacci number.

The time complexity of this function is O(n), because it iterates n-1 times, and the space complexity is O(1), because it uses a constant amount of space to store the variables.