Is it possible to memoize a recursive function without redefining it?

[Maybe I should post this on SO but people are nicer here :hugs:]

I want to apply a memoization function (say mem()) to a recursive function:

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

with something like mem(fib)(n).

That doesn’t work directly, but it does works if the fib function reference is replaced with fib = mem(fib).

I wondered if there was another way to do it, without redefining the original function, thus avoiding side-effects.

I detailed the question in this notebook: Problem with recursion and memoization / Sylvain Lesage / Observable

3 Likes

Well, looking at your notebook… I think you already found a relatively elegant solution to the problem given the circumstances :man_shrugging:. I mean, as far as I can tell:

  • memoization works by wrapping a function in another function that caches the output
  • recursive functions work by calling themselves
  • therefore, the only way to memoize a recursive function must be to replace all recursive calls with calls to the memoized function

… so your approach seems like an obvious one.

One other option I can think of is to modify your original recursive functions to take a callback function to recurse on, then passing them to themselves, and do something like this:

  function fibCB(n, cb) {
    // tangent: I wonder if swapping the
    // order to cb(n-2, cb) + cb(n-1, cb)
    // would be theoretically faster,
    // slower or the same with regards 
    // to initializing the memoization
    return n <= 1 ? 1 : cb(n - 1, cb) + cb(n - 2, cb);
  }
  const memfibCB = mem(fibCB);
  const fib = (n) => fibCB(n, fibCB);
  const memfib = (n) => memfibCB(n, memfibCB);

Note that this introduces extra overhead - if I time fib it’s now slower than the regular fib (~1200 ms versus ~700 ms). The memoized version is still equally fast though.

Also, I just realized that the only reason I came up with this alternate formulation was due to various articles on Reginald Braithwaite’s excellent blog on functional programming in JavaScript:

http://raganwald.com/

Specifically his two-parter on the Y-combinator:

http://raganwald.com/2018/08/30/to-grok-a-mockingbird.html
http://raganwald.com/2018/09/10/why-y.html

Maybe there are some more useful insights relevant to what you’re trying to do in there?

1 Like

Also, just for the record: the naive memoization still kinda works in the sense that after the first successful call it memoizes the result :stuck_out_tongue:

function *perf(fn, ...args) {
  // warm up memoization by calling multiple times
  const result = [], time = []
  for(let i = 0; i < 10; i++){
    var t0 = performance.now();
    const v = fn(args);
    var t1 = performance.now()
    result.push(v);
    time.push(t1 - t0);
    yield { result, time };
  }
}

… but that won’t save you from massive slowdowns for larger input :wink:

1 Like

Thank you for your review! I was hoping some magical solution would allow to apply memoization to any existing recursive function, but as you explain it, something must have been anticipated at the time of writing the function. Afterwards, there seems to be no way to magically add memoization to such functions.

1 Like

sure :slight_smile:

Ok, so… I feel like I just twisted my brain into a shape right out of an M.C. Escher drawing, but I managed to make this:

It’s ridiculously fragile but it seems to work for functions that meet the restrictions.

2 Likes

Yep. And that’s a good thing—if you could change captured values (such as fib’s reference to itself) arbitrarily, the behavior of JavaScript would be even more unpredictable.

I know this wasn’t the point of your question, but JavaScript supports tail call optimization, so one efficient recursive Fibonacci definition (via Antoine Vastel) is:

function fib(n, a = 1, b = 1) {
  return n <= 1 ? a : fib(n - 1, a + b, a);
}
1 Like

Note that only Safari supports tail call optimization (and is therefore the only browser to support ES6).

4 Likes

Well @severo, after first nerd-sniping me into doing an attempt, my notebook in turn nerd-sniped my friend Thomas ten Cate into writing this shorter solution:

It’s a bit cleaner, for sure. Works in different circumstances. Still fragile :stuck_out_tongue:

Here’s a table showing how Safari (and iOS) support tail call elimination, but currently Firefox/Chrome/etc. do not.

https://kangax.github.io/compat-table/es6/#test-proper_tail_calls_(tail_call_optimisation)

Some discussion here https://stackoverflow.com/questions/54719548/tail-call-optimization-implementation-in-javascript-engines

In early 2016, both Safari and Chrome implemented TCE. Safari announced shipping it, while Chrome kept it behind an Experimental Feature flag. […]

At the May 2016 TC39 meeting the issue of tail calls was discussed extensively for almost an entire day with no resolution. Firefox and Edge made clear that they would not implement TCE as specified in the standard. Firefox members proposed to take it out. Safari and Chrome did not agree with that, and the Safari team made clear that they have no intention of unshipping TCE. The proposal for syntactic tail calls was rejected as well, especially by Safari. The committee was in an impasse. You can read the meeting notes of this discussion.

Technically, this impasse still exists today, as far as I am aware. Practically speaking, though, tail calls for JavaScript are pretty much dead, and it’s unclear whether they will ever come back. At least that was the conclusion of the Chrome team after the disastrous meeting, which led to the decision to remove the implementation of tail calls from Chrome, in order to simplify the engine and prevent bit rot. They are still available in Safari.

3 Likes

Thanks to all, I learned a lot reading your comments and references, particularly your notebook @Job!

As a conclusion: I better integrate memoization from start :slight_smile:

2 Likes

The concept of Memoization in Javascript is backed by two main sub-concepts: Closure and High order function. In JavaScript, closures are generated every time a function is created and it allows you access to the domain of the outer function from the inner function. A high order function accepts another function as an argument or returns a function as its output.

This technique is specially useful when it comes to dynamic programming . A memoized function is usually faster because if the function is called subsequently with the previous value(s), then instead of executing the function, would be fetching the result from the cache .