memoize any given recursive function in JavaScript

Question

I am interested in the scenario where we have some function f which is recursive and which we are not provided the source code to.

I would like a function memoizer: Function -> Function which takes in say f and returns a function g such that g = f (in the sense they return the same value given the same arguments) which when called first checks if the called arguments are in its 'cache' (memory of results it has calculated before) and if so returns the result from this, otherwise it should compute f, should f call itself with some arguments, this is tantamount to calling g with those arguments and I would like that f first check if the cache of g contains those arguments and if so return the result from this, otherwise ...

This is easy (in Javascript) to do given the source code of f, I simply define memoize in the obvious way and do something like

let f = memoize((...args) => {/* source code of f */});

But this doesn't appeal to me at all (mainly because I might want a memoized and non memoized version of the same function and then I'd have to write the same function twice) and won't work if I don't know how to implement f.

In case it's not clear what I'm asking,

I would like a function memoize which takes a function such as

fact = n => n === 0 ? 1 : n * fact(n - 1);

And returns some new function g such that fact(n) = g(n) for all n and which for example when g(10) is computed stores the values of fact(0), ..., fact(10) which are computed while computing g(10) and then if I ask for say g(7) it finds the result in the cache and returns it to me.

I've thought that conceptually it's possible to detect when f is called since I have it's address and maybe I could replace all calls to f with a new function where I compute f and store the result and then pass the value on to where it would normally go. But I don't know how to do this (and it sounds unpleasant).

Answer 1

maybe I could replace all calls to f with a new function where I compute f and store the result and then pass the value on to where it would normally go.

This is actually very easy to do, as Bergi referred to in a comment.

// https://stackoverflow.com/questions/24488862/implementing-automatic-memoization-returns-a-closured-function-in-javascript/ 
function memoize(func) {
  var memo = {};
  var slice = Array.prototype.slice;

  return function() {
    var args = slice.call(arguments);

    if (args in memo)
      return memo[args];
    else
      return (memo[args] = func.apply(this, args));

  }
}

function fib(n) {
  if (n <= 1) return 1;
  return fib(n - 1) + fib(n - 2);
}

fib = memoize(fib);

console.log(fib(100));