# #1 Nth Fibonacci

###### tags:`Recursion` `Easy`

## Problem
The Fibonacci sequence is defined as follows: the first number of the sequence is `0` , the
second number is `1`, and the nth number is the sum of the (n - 1)th and (n - 2)th numbers.
Write a function that takes in an integer `n` and returns the nth Fibonacci number.

Important note: the Fibonacci sequence is often defined with its first two numbers as `F0 = 0`
and `F1 = 1`. For the purpose of this question, the first Fibonacci number is `F0`; therefore,
`getNthFib(1)` is equalto `F0` , `getNthFib(2)` is equal to `F1`, etc..

### Sample Input

n = 6

### Sample Output

5 // 0, 1, 1, 2, 3, 5

<br>

:::spoiler **Optimal Space & Time Complexity**

O(n) time | O(1) space- where n is the input number

:::

<br>

:::spoiler Hint 1
The formula to generate the nth Fibonacci number can be written as follows: F(n) = F(n - 1) + F(n - 2). Think of the case(s) for which this formula doesn't apply (the base case(s)) and try to implement a simple recursive algorithm to find the nth Fibonacci number with this formula
:::

<br>

:::spoiler Hint 2
What are the runtime implications of solving this problem as is described in Hint 1? Can you use memoization (caching) to improve the performance of your algorithm?

:::

<br>

:::spoiler Hint 3
Realize that to calculate any single Fibonacci number you only need to have the two previous Fibonacci numbers. Knowing this, can you implement an iterative algorithm to solve this question, storing only the last two Fibonacci numbers at any given time?
:::

<br>

<hr/>

## Solutions

### Official

#### Solution 1 : pure recursion

// O(2^n) time | O(n) space
fuction getNthFib(n){
    if (n === 2) {
        return 1;
    } else if (n === 1) {
        return 0;
    } else {
        return getNthFib(n - 1) + getNthFib(n - 2);
    }
}

<br>

#### Solution 2: recursion with hashmap storing calculated fib value

// O(n) time | O(n) space
fuction getNthFib(n, memoize = {1: 0, 2: 1}){
    if (n in memoize) {
        return memoize[n];
    } else {
        memoize[n] = getNthFib(n - 1, memoize) + getNthFib(n - 2, memoize);
        return memoize[n]
    }
}

<br>

#### Solution 3: not using recursion

// O(n) time | O(1) space
fuction getNthFib(n){
    const lastTwo = [0, 1];
    let counter = 3;
    while (counter <= n) {
        const nextFib = lastTwo[0] + lastTwo[1];
        lastTwo[0] = lastTwo[1];
        lastTwo[1] - nextFib;
        counter ++;
    }
    return n > 1 ? lastTwo[1] : lastTwo[0];
}

<br>

---

### Everyone's

#### Pure recursion

:::spoiler 月

// Time O(n) Space O(n)
function getNthFib(n) {
  if(n === 1) return 0;
  else if(n === 2) return 1;
  return getNthFib(n - 1) + getNthFib(n - 2);
}

- Time complexity should be `O(2^n)`

:::

<br>

:::spoiler Hao

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

:::

<br>

:::spoiler YC

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

:::

<br>

#### Recursion with hash map

:::spoiler 東

// Time O(n) | Space O(n); where n is the input n
function getNthFib(n) {
  const FibHashMap = { 1: 0, 2:1 };
  if(n in FibHashMap) return FibHashMap[n];
  else FibHashMap[n] = getNthFib(n-1) + getNthFib(n-2);
  return FibHashMap[n];
}

:::

<br>

---

## Supplement / Discussion

### Memoization

#### What is Memoization?

:::success
In programming, memoization is an optimization technique that makes applications more efficient and hence faster. It does this by **storing computation results in cache**, and **retrieving that same information from the cache the next time** it's needed instead of computing it again.
:::

- In simpler words, it consists of storing in cache the output of a function, and making the function check if each required computation is in the cache before computing it.

- A cache is simply a temporary data store that holds data so that future requests for that data can be served faster.

- Memoization is a simple but powerful trick that can help speed up our code, especially when dealing with repetitive and heavy computing functions.

(Apply in Dynamic Programming)

:arrow_right: [Memoization Reference link](https://www.freecodecamp.org/news/memoization-in-javascript-and-react/#:~:text=In%20programming%2C%20memoization%20is%20an,instead%20of%20computing%20it%20again.)