# Recursion with memoization in Typescript

## What are recursive functions?
A recursive function is a function that calls itself until a condition is met. Recursive functions are especially useful when a problem can be solved by solving subsets of the problem, or sub-problems, and aggregating the results in some way. The same function is used with the sub-problem as the input, which is broken down further until the problem can be solved easily. The problem for which the solution is trivial is the base case, without which the function does not terminate.

Examples of problems where recursion is useful include:
- Tree traversal
- Searching graphs
- Sorting algorithms
- Machine learning and Artificial Intelligence

## Fibonacci sequence
The Fibonacci sequence is a series of numbers where the next number in the series is the sum of the two numbers before it.

`{0, 1, 1, 2, 3, 5, 8, 21, 34, ...}`

The formula for the \\(n^{{th}} \\) number in the Fibonacci sequence is:
\\[F(0) = 1, F(1) = 1 \\]



\\[ F(n) = F(n-1) + F(n-1)\\]

This is a perfect use case for recursion as the function is defined recursively. The base case for this instance is where `n` is less than 2, in which case the function returns `n`. The typescript code is listed below:

``` typescript
let fibonacci = (n: number): number => {
  if (n < 2) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
};
```

This code works fine for small numbers, but as `n` increases, the number of function calls increases exponentially. Trying to compute `fibonacci(50)` takes too long and causes my computer to crash. This is where memoization comes in.

## Memoization
In the above code, the function is called with input 1 for every pass of the function call, so it is called `fibonacci(n)` times. The same happens for each number `i` below `n` where the function is recomputed `fibonacci(n - i + 1)` times. This is unnecessary, as it's value is already known after the first function call. Memoization is a technique where the value of the function call for a certain input is saved the first time it's called and therefore does not have to be recomputed.

In typescript, we can use a Map to store the computed value for a input value and then retrieve it for subsequent calls.
```typescript
let fibonacci = (n: number, cache: Map<number, number> = new Map()): number => {
  if (cache.has(n)) {
    return cache.get(n) || 0;
  }
  if (n < 2) {
    return n;
  }
  const result = fibonacci(n - 1, cache) + fibonacci(n - 2, cache);
  cache.set(n, result);
  return result;
};
```
This approach is great and allows me to compute `fibonacci(1400)` on my computer in barely no time. The constraint this time is that the number becomes greater than `2^1024` and is therefore `infinity` in JavaScript. Adding the memoization code, however, results in code that is not obvious at first glance as to its function.

## Memoization Function

We can therefore extract a generic `memoize` function that can be applied to any function where you want to save value of a function call. The `memoize` function will therefore take a function and return another a similar function with memoization behavior. 

```typescript
const memoize = <T = any>(fn: Function) => {
  const cache = new Map();
  return function (val: T) {
    if (!cache.has(val)) {
      cache.set(val, fn(val));
    }
    return cache.get(val);
  };
};

let fibonacci = (n: number): number => {
  if (n < 2) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
};

fibonacci = memoize(fibonacci);
fibonacci(10);
```
The `fibonacci` function is overwritten with the memoized version to ensure that the recursive references are also memoized. Calling `memoize(fibonacci)(10)` would not result in complete memoization. The correct approach would be:
``` typescript
fibonacci = memoize(fibonacci);
fibonacci(10);
```