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.