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 ?
Advertisement
Answer
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; } }