# Problem 509 - Fibonacci Number

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)`.

This problem is a great introduction to recursion and a little fun concept called dynamic programming (DP).

## Conceptual Overview

In mathematics, the Fibonacci numbers form a sequence called the Fibonacci sequence, such that each number is the sum of the two preceding ones starting from 0 and 1.

For example: 0, 1, 1, 2, 3, 5, ...

So how do we solve this? I mentioned earlier that this problem is an introduction to recursion and DP. It is, but there are a few ways we can solve this problem.

If you want to learn more about Dynamic Programming, check out Dynamic Programming I: Fibonacci, Shortest Paths from MIT OpenCourseWare.

So there are a few solutions:
1) Recursion
2) Recursion with DP
3) Iteratively

Each with different time and space complexities.

## Coding walkthrough

### Recursion only

Any function that uses Recursion you must remember that there needs to be a base condition to stop the recursion. If the base case is not reached or defined then there will be stack overflow due to memory limitations.

``````/**
* @param {number} N
* @return {number}
*/
const fib = (N) => {
if (N < 2) return N; // base condition

return fib(N - 2) + fib(N - 1); // recursion
};
``````

Pretty straight forward, there's a base condition that will stop the recursion when it evaluates to true.

#### Time & Space Complexity

Time: O(2^N) & Space: O(N)

### Memoized dynamic programming algorithm

``````/**
* @param {number} N
* @return {number}
*/
const fib = (N) => {
let memo = {}
memo = 0 // Given
memo = 1 // Given

if (N in memo) return memo[N] // Base condition
else  {
memo[N] = fib(N - 1) + fib(N - 2) // Memoize results
return memo[N]
}
};
``````

Whenever we compute a Fibonacci number we put it into the hash table. We do this to "store" or memorize the value so we do not have to do the calculation again. We can look up the key-value in constant time.

#### Time & Space Complexity

This would be considered a top-down approach
Time: O(N) & Space: O(N)

### Iterative approach

``````const fib = (N) => {
const lastTwo = [0, 1]
let counter = 3

if (N <= 1) {
return N;
}
if (N == 2) {
return 1;
}

while (counter <= N) {
const nextFib = lastTwo + lastTwo
lastTwo = lastTwo
lastTwo = nextFib
counter++
}

return lastTwo + lastTwo
};
``````

#### Time & Space Complexity

Time: O(N) & Space: O(1)