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:

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.

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.

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:

fibonacci = memoize(fibonacci);
fibonacci(10);