Fibonacci Sequence

Implement a function that returns the Fibonnaci number for a given integer input. In a Fibonacci sequence, each number is the sum of the two preceding ones.

The simplest is the series: 1, 1, 2, 3, 5, 8, etc.

This is because:

fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(2) = 1
fibonacci(3) = 1 + 1 = 2
fibonacci(4) = 1 + 2 = 3
fibonacci(5) = 2 + 3 = 5

So if we were to invoke fibonacci(5), we'd want to return 5 (because the second to last number was 2 + last number was 3).

Constraints

• The value of n will always be a non negative integer and <=40
• The answer is guaranteed to fit in the integer data type
• Expected time and space complexity are both O(n)

```js
/*
 * @param {number} n The Fibonacci number to get.
 * @returns {number} The nth Fibonacci number
 */

function fibonacci(num) {
  // fill this in
  return num;
}
```

Recall the definition of the Fibonacci numbers: they are a sequence of integers in which every number after the first two (0 and 1) is the sum of the two preceding numbers. To arrive at the sequence, we can quickly recognize there's a pattern in place, where we are repeating a similar calculation multiple times with different numbers.

Time to reach into our toolbox-- this can readily be solved with recursion. At each recursive call, run the same calculation based off the same function for the prior elements. You can see the pseudo-code provided for how this can be accomplished.

```
Routine: f(n)
Output: Fibonacci number at the nth place

Base case:
1. if n==0 return 0
2. if n==1 return 1

Recursive case:
1. temp1 = f(n-1)
2. temp2 = f(n-2)
3. return temp1+temp2
```

So we know we simply recursively call a method that returns the sum of the previous two fibonacci numbers.

If we look closely at the recursive tree, we can see that the function is computed twice for f(3), thrice for f(2) and many times for the base cases f(1) and f(0). The overall complexity of this pseudo-code is therefore exponential O($2^n$). We can very well see how we can achieve massive speedups by storing the intermediate results and using them when needed.

```
Routine: fibonacciFast
Input: n
Output: Fibonacci number at the nth place
Intermediate storage: n1, n2 to store f(n-1) and f(n-2) respectively

1. if (n==0) return 0
2. if (n==1) return 1
3. n1 = 1
4. n2 = 0
5. for 2 .. n
    a. result = n1+n2           // gives f(n)
    b.   n2 = n1                // set up f(n-2) for next number
    c.   n1 = result            // set up f(n-1) for next number
6. return result


```

To memo-ize previous function calls, we can use a nifty memoize function.

What we're doing in memoize is utilizing a hash map (in this case, a plain old JS object) to store previous calculations. The key will be the arguments called-- for example, 5 in fib(5), and the value attached will be the result of the callback. In this example, we utilize the closure pattern so that ...args are the parameters of the callback function, and not of memoize.

```js
const memoize = (callback) => {
  let memo = {};
  return (...args) => {
    if (memo[args]) {
      return memo[args];
    } else {
      memo[args] = callback(args);
      return memo[args];
    }
  };
};
```
```py
class Memoize:
    def __init__(self, func):
        self.func = func
        self.memo = {}
    def __call__(self, *args):
        if not args in self.memo:
            self.memo[args] = self.f(*args)
        return self.memo[args]
```

Now we can wrap our fibonacci function with the memoize function for a more efficient solution. During an interview, it's best to bring up the use of this pattern whenever there's several repeating subproblems.

```js
const memoize = (callback) => {
  let memo = {};
  return (...args) => {
    if (memo[args]) {
      return memo[args];
    } else {
      memo[args] = callback(args);
      return memo[args];
    }
  };
};

function fibonacci(num) {
  if (num < 0) throw "num must be >= 0";
  if (num === 0) return 0;
  if (num === 1) return 1;

  return fibonacci(num - 1) + fibonacci(num - 2);
}

const memoizedFib = memoize(fibonacci);
const result = memoizedFib(30);
console.log(result);
```
```py
class Memoize:
    def __init__(self, func):
        self.func = func
        self.memo = {}
    def __call__(self, *args):
        if not args in self.memo:
            self.memo[args] = self.func(*args)
        return self.memo[args]

def fibonacci(num):
    if num < 0:
        raise "num must be >= 0"
    if num == 0:
        return 0
    if num == 1:
        return 1

    return fibonacci(num - 1) + fibonacci(num - 2)

memoized_fib = Memoize(fibonacci)
print(memoized_fib(30))
```

One Pager Cheat Sheet

• Implement a function fibonacci(n) which returns the number in the Fibonacci sequence where n <= 40, with a time and space complexity of O(n).
• The Fibonacci sequence can be effectively generated using Recursion in order to efficiently calculate each successive number from the sum of the two prior.
• By storing intermediate results and using a recursive approach, the Fibonacci Sequence can be calculated with a complexity of `O($2^n$)$.
• We can memo-ize (store) previous function calls and their results by using the memoize function, which uses a hash map as a storage.
• To improve performance in recurring algorithms, use memoize to wrap the fibonacci function.