Memoization: a use case
Hi there! How are you? I hope you are well!
Well, I came up across a very interesting course of Stephen Grider on uDemy about Algorithms and Data Structures!
I want to jot down here a piece of this course about optimizing a recursive function and what better example than the Fibonazzi sequence!
Here is the code for the recursive version of Fibonazzi:
function fib(n) {
if (n < 2) {
return n
}
return fib(n - 1) + fib(n - 2)
}
The problem with this function is that it runs with the same inputs several times and as the input increases the number of calls to the functions increase exponentially, that’s why the Big O notation for this is O(2^n), which is not a good thing!
For example, a call to fib(3) would call fib(2) which would call fib(1) and f(0). A call to fib(4) would call again fib(3), which would call fib(2), which would call fib(1) and fib(0). But, it would also call fib(2) again etc making a tree of fib calls with repeating nodes!!
The solution to optimize our code comes with a high-order function which we call memoize that takes the fib function as a parameter and returns a new optimized version, with unique new calls to the fib function! I know everything sounds super weird (but they are). The implementation of this function is as follows:
function memoize(fn) {
const cache = {}
return (...args) => {
if (cache[args]) {
return cache[args]
}
const result = fn.apply(this, args)
cache[args] = result
return result
}
}
Then we can simply make copy of our function like this:
const optFib = memoize(fib)
Doing this we reduce the number of calls to n time or in Big O notation to O(n) or from exponential runtime to linear!
Simple code but with extremely condensed notions!
Cheers!
PS: in case you were wondering like me what exactly is …args check out this page here for more info:
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Functions/rest_parameters