Memoizing recursive functions

memoize-recursive.js

const memoizeFactory = hashFn => fn => {
  const memoize = fn => {
    const cache = {};

    return (...args) => {
      const key = hashFn(args);
      if (key in cache) {
        return cache[key];
      }

      return cache[key] = fn(...args);
    };
  };

  const newDefinition = `
    return memoize => {
      const ${fn.name} = memoize(${fn.toString()});
      
      return ${fn.name};
    };
  `;

  return new Function(newDefinition)()(memoize);
};

export default memoizeFactory;

Je sais, vous pourriez absolument faire quelque chose de ce genre :

const fib = memoize(n => n < 2n ? n : fib(n - 1n) + fib(n - 2n));

Ici, fib fait directement référence à la fonction mémoïsée et ce serait la façon recommandée de faire.

Cela dit, avec memoFactory, vous pourriez importer une fonction récursive non mémoïsée d'un autre package et faire ceci :

const memoize = memoizeFactory(x => x);
const memoFib = memoize(fib);

Cool, n'est-ce pas ? 😄

Voici quelques tests jsperf : https://jsperf.com/memoize-fibonacci

Si vous voulez en savoir plus sur la mémoïsation, vous pouvez lire cet article.