# LeetCode 509. Fibonacci Number — Using Recursion in JavaScript

This week has not been any different than the past few weeks as I have been studying more and more to be better prepared for upcoming interviews. This week the problem I decided to spotlight is another easy problem from LeetCode. Problem 509 is titled Fibonacci Number.

# The Problem:

The **Fibonacci numbers**, commonly denoted `F(n)`

form a sequence, called the **Fibonacci sequence**, such that each number is the sum of the two preceding ones, starting from `0`

and `1`

. That is,

`F(0) = 0, F(1) = 1`

F(N) = F(N - 1) + F(N - 2), for N > 1.

Given `N`

, calculate `F(N`

# My Solution:

A simple solution for the problem is to use recursion but by using recursion you will sacrifice efficiency. To begin we have to check for two base cases one where if the number that is passed in is less than or equal to zero and if the number passed in is equal to one. The final case will be to call the function on itself but add n-1 plus n-2. All together the solution will become:

`let fib = function(N) {`

if (N <= 0) {

return 0;

} else if (N === 1) {

return 1;

} else {

return fib(N-1) + fib(N-2)

}

};

Runtime: **112 ms**

Memory Usage: **38.3 MB**