Fibonacci Recursive Memoization

Base Implementation

Looking at the recursive Fibonacci implementation below:

export const fib = (n: number): number => {
  if (n <= 2) return 1;
  return fib(n - 1) + fib(n - 1);
};

The time complexity is $O(2^n)$ and space complexity of $O(n)$

The above function gets extremely slow when n is large due to the recursive implementation. For example asking for fib(50) will have a time of $2^50$

If we visualize the implementation of the above function we will see a tree, for example for n=7:

Looking at the subtrees we can see that there is a lot of data that is frequently recalculated and we can try to memoize this data

With Memoization

We can create a memo object that we pass around that will allow us to access and early escape a calculation

export const fib = (n: number, memo: Record<number, number> = {}): number => {
  if (n in memo) return memo[n];

  // rest of existing implementation with passing the memo
  if (n <= 2) return 1;
  const result = fib(n - 1, memo) + fib(n - 1, memo);

  // memoize the existing value and return it
  memo[n] = result;
  return result;
};

And now running fib(50) runs super quickly, this essentially takes the tree and collapses it into a more linear implementation and looks a bit like this:

Based on this, the time complexity is now $O(n)$ without a relevant impact on the space complexity which is still $O(n)$