Functional Memoization is a technique which makes a function call faster by trading space for time. Memoize caches the return values of the function, so if the function is called again with the same arguments, Memoize jumps in and returns the cached value, instead of letting the function compute the value all over again.
The term was first coined by the scientist Donald Mitchie in 1968. He proposed using Memoized Functions to improve performance of Machine Learning and it’s became more popular in recent years with the rise of Functional Programming.
A Pure Function is the one that
- Returns same output for the same input, every time.
- Doesn’t depend on and doesn’t modify the state of the variables out of its scope. This includes having no side-effects like logging(console.log) or any DOM manipulation.
A Pure Function
An Impure Function
Slice and Splice do the same thing to the array but in a different way, slice returns a new array according to the input, guaranteeing the same output per input every time. Splice on the other hand modifies the original array and the same output per input is not guaranteed.
Slice(without a ‘p’) is pure and can be memoized but Splice(with a ‘p’) is impure and cannot be memoized.
So, it makes sense that memoization does not works for Impure Functions, because if the function does not return same value for the same input the returned cached value will not be the required result. It’ll make more sense when we memoize some stuff.
Memoization works great with recursive functions, as the Recursive functions are called again and again. So let’s memoize the famous recursion of the classic factorial function. But first, we have to define a memoize function which takes another function and caches its calls.
Okay, now we are prepared, let’s start memoizing…
Okay okay, This is what happened
When factorial(3) is called, functions factorial(2) and factorial(1) are also called because of recursion. But when factorial(3) is called again the memoize function simply retuned the cached result, so no recursion happened.
In case of factorial(4), the function returned the calculated value from cached result of factorial(3), stopping the further recursion.
Memoization can potentially increase performance by caching the results of previous function calls but they are not ideal for fast executing functions.