Creé una función withMemo que devuelve una versión memorizada de la función proporcionada.
const memoizedFn = withMemo(fn)¿Cómo puedo memorizar esta función de fibonacci que funciona con recursividad?
const fibo = (n) => { if (n <= 1) return 1 return fibo(n - 2) + fibo(n - 1) } De hecho withMemo(fibo) no mejora el rendimiento ya que las llamadas recursivas dentro de fibo todavía apuntan a la versión no memorizada...
Así que tengo que alterar la declaración de fibo para que la momoización funcione:
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 ¿Hay alguna forma de memorizar fibo (o cualquier otra función recursiva) sin alterar su declaración como lo hice yo?
Puede usar let fibo en lugar de const fibo . Luego reemplace la variable fibo con una versión memorizada. Al actualizar fibo , la llamada anidada ahora se referirá a la función fibo memorizada en lugar del 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; } }