Well, looking at your notebook… I think you already found a relatively elegant solution to the problem given the circumstances . 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:
Also, just for the record: the naive memoization still kinda works in the sense that after the first successful call it memoizes the result
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 };
}
}
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.
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);
}
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
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.
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 .
]
. I mean, as far as I can tell:
