I created a withMemo function that returns a memoized version of the provided function.
const memoizedFn = withMemo(fn)
How can I memoize this fibonacci function that works with recursion ?
const fibo = (n) => {
if (n <= 1) return 1
return fibo(n - 2) + fibo(n - 1)
}
Indeed withMemo(fibo) doesn't improve performance since the recursive calls inside fibo still point to the unmemoized version...
So I have to alter the declaration of fibo to make momoization work:
const momoizableFibo = memoizer => {
const fibo = (n) => {
if (n <= 1) return 1
return memoizer(fibo)(n - 2) + memoizer(fibo)(n - 1)
}
return memoizer(fibo)
}
// momoizableFibo(withMemo)(50) // takes a ms
Is there a way to memoize fibo (or any other recursive function for that matter) without altering it's declaration in the way I did ?
You can use let fibo instead of const fibo. Then replace the fibo variable with a memoized version. By updating fibo the nested call will now refer to the memoized fibo function instead of the original.
let fibo = (n) => {
console.log(n); // <- show original fibo calls
if (n <= 1) return 1;
return fibo(n - 2) + fibo(n - 1);
}
// update fibo variable so the nested fibo call calls the memoized version
fibo = withMemo(fibo);
console.log("fibo(3)", "//=>", fibo(3));
console.log("fibo(5)", "//=>", fibo(5));
console.log("fibo(2)", "//=>", fibo(2));
// simplified memoize function, only works for serializable parameters
function withMemo(fn) {
const cache = new Map();
return function (...args) {
const key = JSON.stringify(args);
if (cache.has(key)) return cache.get(key);
const result = fn(...args);
cache.set(key, result);
return result;
}
}