Memoization is a specific form of caching used in dynamic programming. Caching is a way to speed our programs and hold some data in an accessible box for later use. It stores the pre-computed value and returns the value instantaneously if the given input is seen before.
In addition, memoization is an optimization technique in caching results when the same set of arguments result in the same output and lead to performant web applications.
Fibonacci sequence
Let's write a function to compute the Fibonacci sequence without memoization.
The Fibonacci sequence represents a list of numbers where each value is the sum of the two previous values. The first two elements of the sequence are 0 and 1.
// fibonacci without memoization
const fib = (num) => {
if (num < 2) {
return 1
} else if (!num || typeof num !== 'number') {
return 'value must be a number!'
}
return fib(num - 1) + fib(num - 2)
}
console.log(fib(10))
From the code above, we have a function that generates the sum of two previous values. Since the function is pure, num as the given value of the argument in fib() will return the same value. Therefore, we have a recursive function in this code sample in the return condition. Suppose fib() caches the results. In that case, as we will see later on, the program's performance could have given a quicker response because we could have stored the previous result of the sequence instead of running the calculation all over.
Memoizing the fibonacci function
In the example below, we will see how the fib() function memoizes its given input.
// fibonacci sequence with memoization to run the function fib()
const fib = (num) => {
let cache = {}; // set cache
// if exists in cache return from cache
if (cache[num] !== undefined) {
console.log(`${num} is cached!`);
return cache[num];
}
// if not in cache perform operation
cache[num] = num < 2 ? 1 : fib(num - 1) + fib(num - 2);
return cache[num];
}
const result = fib(5)
console.log(result) // 8
In the code snippet above, we created a cache object that the fib() uses to store its output value. Each time fib() is invoked, it checks whether the fib() of input num has been stored previously in the cache object. If it has, it immediately returns the cached value.
Now computing fib(5) after fib(10) will significantly speed up the program's performance as fib(5) in the function is calculated as part of fib(10), which leads to efficient code.
The time it takes when caching is halved once the function recognizes a given input declared in the program before.
Exercise
Let's find the factorial of a given number using the cache execution of a factorial() function.
// factorial of a number with memoization (cache execution)
const factorial = (num) => {
let cache = {}; // set cache
// if cache already exists, return cache
if (cache[num] !== undefined) {
console.log(`${num} is cached!`);
return cache[num];
// edge case validation for not a number
} else if(!num || typeof num != 'number') {
return `value must be a number`
}
cache[num] =
num === 0
? 1 : num === 2 ? 2
: num * factorial(num - 1); // condition ternary operator, same with if/else statement
return cache[num];
};
console.log(factorial(5)); // 120