# Fibonacci Recursive Memoization

Updated: 01 February 2024

# Base Implementation

Looking at the recursive Fibonacci implementation below:

dynamic-programming/memoization/fib.ts
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

dynamic-programming/memoization/fib-memo.ts
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)$