Let's solve LeetCode! Fibonacci Number

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] = 0 // Given
    memo[1] = 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[0] + lastTwo[1]
        lastTwo[0] = lastTwo[1]
        lastTwo[1] = nextFib
        counter++
    }

    return lastTwo[0] + lastTwo[1]
};

Time & Space Complexity

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