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;

Yes, you can definitely write something like:

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

Here, fib directly references the memoized function and it would be the recommended way to proceed.

With memoFactory however, you can import another recursive function that has not been memoized yet and do this:

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

Cool, isn't it? 😄

Here are some jsperf tests: https://jsperf.com/memoize-fibonacci

If you want to learn more about memoization, you can read this article.

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.