How to decorate a recursive function with caching in JavaScript?

Question

We're going to make a decorator, caching computed results of deterministic functions (for simplisity let's assume one-argument functions).

In common case is could be done this way:

function makeCacheable(origFunc){
  let registry = {};

  return function (a){
    if (a in registry){
      return registry[a];
    }

    let res = origFunc(a);

    registry[a] = res;

    return res;
  }
}

A problem appears when origFunc is recursive: only top-level calls go through the wrapping cache, but the rest of recursive call stack doesn't meet the cache. No need to explain why this happens. I wonder is there a natural way to make a recursive function cacheable in the same manner?

function fibonacciF(n) {
  if (n <= 2) return 1;

  let a = 1, b = 1;

  for (let i = 2; i < n; ++i){
    [a, b] = [b, a+b];
  }

  return b;
}

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

let fiboF = makeCacheable(fibonacciF); // OK
let fiboR = makeCacheable(fibonacciR); // actually is not what expected

Answer 1

You could make it work, if you would use the same (function) variable for storing the decorated version of it. To allow for returning back to the original, you could add a property original to the function object:

function makeCacheable(origFunc){
  let registry = {};
  let f = function (a){
    if (a in registry){
      console.log(`retrieving value from registry[${a}]`);
      return registry[a];
    }
    let res = origFunc(a);
    registry[a] = res;
    return res;
  }
  // Add property for exposing the original function:
  f.original = origFunc;
  return f;
}

function fibonacciR(n) {
  console.log(`Called fibonnacci(${n})`);
  return n <= 2 ? 1 : (fibonacciR(n-1) + fibonacciR(n-2));
}

// Demo illustrating the registry is being used:
console.log('Call fibonnacciR(5) with cache turned on:');
var fibonacciR = makeCacheable(fibonacciR);
var f5 = fibonacciR(5);
console.log(`Result: fibonnaciR(5) = ${f5}`);

// Demo illustrating the function can be restored:
console.log('Call fibonnacciR(5) with cache removed:');
fibonacciR = fibonacciR.original;
f5 = fibonacciR(5);
console.log(`Result: fibonnaciR(5) = ${f5}`);

.as-console-wrapper { max-height: 100% !important; top: 0; }