How do I make this higher-order memoization function work for recursive functions?

Question

I have a basic memoization function written as

function memo(func) {
  const cache = new Map()

  return function (...args) {
    const cacheKey = args.join('-')
    if (!cache.has(cacheKey)) {
      const value = func(...args)
      cache.set(cacheKey, value)
      return value
    }

    return cache.get(cacheKey)
  }
}

It doesn't work with functions that recursively calls itself. For example:

const fibonacci = (n) => {
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
}

const memoizedFib = memo(fibonacci)
memoizedFib(20)

Here inside fibonacci, it still does a lot of duplicate calculations.

I guess a way to avoid that is to insert the memoization into the implementation for the function.

const cache = new Map();
const memoFibonacci = (n) => {
  if (memory.has(n)) return memory.get(n);
  if (n <= 1) return 1;
  const result = memoFibonacci(n - 1) + memoFibonacci(n - 2);
  memory.set(n, result);
  return result;
};

I wonder if there is a way to make the higher order util function work with recursive functions like fibonacci?

I was several minutes into writing a solution that included the recursion depth as part of the cache key until @VLAZ popped in with the absolutely inspired solution in the comment above. — Alexander Nied, Mar 03 '22 at 06:38
Unrelated, but that memoization function will [not work well](https://stackoverflow.com/q/70968429/5459839) when there are argument(s) that do not stringify in a unique way, or have hyphens in them. — trincot, Mar 03 '22 at 06:39
@Alexander Nied I would still like to see your approach as well! — Joji, Mar 13 '22 at 02:31
@trincot thanks for pointing that out. Do you have any suggestions about how to fix it? — Joji, Mar 13 '22 at 02:32

VLAZ · Accepted Answer · 2022-03-03T07:34:46.147

Here is a non-memoised recursive function as a benchmark:

const fibonacci = (n) => {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
}

const result = fibonacci(5);

console.log("result:", result);

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

Directly define a memoised function

You can define the function and memoise which would make all recursive calls use the memoised version:

How it looks

const fibonacci = memo((n) => {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
});

Demo

function memo(func) {
  const cache = new Map()

  return function (...args) {
    const cacheKey = args.join('-')
    if (!cache.has(cacheKey)) {
      const value = func(...args)
      cache.set(cacheKey, value)
      return value
    }

    return cache.get(cacheKey)
  }
}

const fibonacci = memo((n) => {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
});

const result = fibonacci(5);

console.log("result:", result);

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

Replace original with memoised

You can also memoise it later by replacing the original binding for it. For this to work, the function should not be defined as const. This would still make future calls use the memoised version:

How it looks

let fibonacci = (n) => {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
};

fibonacci = memo(fibonacci);

OR

function fibonacci(n) {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
};

fibonacci = memo(fibonacci);

Demo

function memo(func) {
  const cache = new Map()

  return function (...args) {
    const cacheKey = args.join('-')
    if (!cache.has(cacheKey)) {
      const value = func(...args)
      cache.set(cacheKey, value)
      return value
    }

    return cache.get(cacheKey)
  }
}

let fibonacci = (n) => {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
};

fibonacci = memo(fibonacci);

const result = fibonacci(5);

console.log("result:", result);

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

Warnings

Be aware that this will only work for recursive functions that refer to a binding that you can control. Not all recursive functions are like that. Few examples:

Named function expressions

For example if the function is defined with a local name which only it can use to refer to itself:

How it looks

let fibonacci = function fibonacci(n) {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
};

fibonacci = memo(fibonacci);

Demo

function memo(func) {
  const cache = new Map()

  return function (...args) {
    const cacheKey = args.join('-')
    if (!cache.has(cacheKey)) {
      const value = func(...args)
      cache.set(cacheKey, value)
      return value
    }

    return cache.get(cacheKey)
  }
}

let fibonacci = function fibonacci(n) {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
};

fibonacci = memo(fibonacci);

const result = fibonacci(5);

console.log("result:", result);

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

This is because the name of the function expression is usable in the body of the function and cannot be overwritten from the outside. Effectively, it is the same as making it:

let fibonacci = function recursive(n) {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return recursive(n - 1) + recursive(n - 2)
};

fibonacci = memo(fibonacci);

Inner functions

It would also not work for functions that use an inner recursion helper:

let fibonacci = (n) => {
  const fibonacciHelper = (n) => {
    console.log(`fibonacci(${n})...`);
    if (n <= 1) return 1;
    return fibonacciHelper(n - 1) + fibonacciHelper(n - 2)
  }
  
  return fibonacciHelper(n);
};

fibonacci = memo(fibonacci);

Demo

function memo(func) {
  const cache = new Map()

  return function (...args) {
    const cacheKey = args.join('-')
    if (!cache.has(cacheKey)) {
      const value = func(...args)
      cache.set(cacheKey, value)
      return value
    }

    return cache.get(cacheKey)
  }
}

let fibonacci = (n) => {
  const fibonacciHelper = (n) => {
    console.log(`fibonacci(${n})...`);
    if (n <= 1) return 1;
    return fibonacciHelper(n - 1) + fibonacciHelper(n - 2)
  }
  
  return fibonacciHelper(n);
};

fibonacci = memo(fibonacci);

const result = fibonacci(5);

console.log("result:", result);

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

Modules / other scopes

If you do not have access to the definition of the function, then you cannot really control the binding it uses to call itself. Easiest to see when using modules:

How it looks

fibonacci.js

export let fibonacci = (n) => {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
}

index.js

import { fibonacci as fib } from "./fibonacci.js"

//assume memo() exists here

let fibonacci = memo(fib);
fibonacci(5);

This will not affect the recursive function since it still refers to itself from the module scope.

the Hutt · Answer 2 · 2022-03-13T07:57:29.753

Note: this doesn't cover all the possibilities mentioned in @VLAZ's answer. Just stating one possible way. Also, using eval() is not a good idea.

With this we don't have to replace the original function:

function memo(func) {
  const cache = new Map()
  let myFunc = null;
  let funcDef = func.toString().replaceAll(func.name, 'myFunc');
  func = eval(`(${funcDef})`);

  myFunc = function(...args) {
    const cacheKey = args.join('-')

    if (!cache.has(cacheKey)) {
      const value = func(...args)
      cache.set(cacheKey, value)
      return value
    }
    return cache.get(cacheKey)
  }

  return myFunc;
}


// Demo
let fibonacci = (n) => {
  console.log(' ', n);
  if (n <= 1) return 1;
  return fibonacci(n - 1) + fibonacci(n - 2)
}

const memoizedFib = memo(fibonacci);
console.log('memoizedFib(3)');
console.log('result: ', memoizedFib(3));

console.log('memoizedFib(4): ');
console.log('result: ', memoizedFib(4));

// we can still use original fibonacci function
console.log('fibonacci(4): original function ');
console.log('result: ', fibonacci(4));


const sum = (n) => {
  console.log(' ', n);
  if (n <= 1) return 1;
  return sum(n - 1) + n;
}

const memorizedSum = memo(sum);
console.log('memorizedSum(3): ');
console.log('result: ', memorizedSum(3));
console.log('memorizedSum(5): ');
console.log('result: ', memorizedSum(5));

To support non-arrow functions we can retrieve their code and convert them to arrow functions using eval.

thanks for the answer. This is certainly an interesting solution. You said "it doesn't cover all the possibilities mentioned in @VLAZ's answer", what are some possibilities we are missing here? — Joji, Mar 13 '22 at 14:33
It won't work for `let fibonacci = function fibonacci(n) {...}` for the reasons explained by @VLAZ. Getting around this can be done by converting the function code string to arrow function string and then doing `eval()`. Also, for inner helper functions it won't work. There are so many ways a dev can implement a simple recursion. But, If you can modify the recursive functions or you are implementing them yourself then, other approach could be to pass function references as parameters for recursion. And while calling the function pass memorized refs. — the Hutt, Mar 13 '22 at 16:19

score 0 · Answer 3 · answered Mar 19 '22 at 21:49

that memoization function will not work well when there are argument(s) that do not stringify in a unique way, or have hyphens in them

@trincott is right and a solution to that would be to have a Map based "linked list" of sorts which I demonstrate below

@VLAZ already covered the memoization and to emphasise, this answer is simply to hold the various types of arguments that may exist in a list of arguments

let unknown=Symbol(null) //a symbol for a value NOT EXISTING
/*example structure of list(the only known arguments are [], [5,9] and [5,2]):
OBJECT{
  value:'nothing',
  next:MAP{
    5:OBJECT{
      value:unknown, //[5] isn't a recorded argument
      next:MAP{
        9:OBJECT{
          value:59,
          next:MAP{}
        },
        2:OBJECT{
          value:52,
          next:MAP{}
        }
      }
    }
  }
}
yes, so the result for arguments [arg1,arg2,arg3] would be list->arg1->arg2->arg3
*/
function read(args,head){ 
  for(let i=0;i<args.length;i++){
    if(!(head=head.next.get(args[i]))){return false}
  }
  return head.value!==unknown?head:false
}
function write(args,head,value){
  for(let i=0;i<args.length;i++){
    let nextPathValue=head.next.get(args[i])
    if(!nextPathValue){
      head.next.set( args[i],{value:unknown,next:new Map()} )
      head=head.next.get(args[i])
    }
    else{head=nextPathValue}
  }
  return head.value=value
}
function memo(func) {
  const list = {value:unknown,next:new Map()}
  return function () {
    let existing=read(arguments,list)
    if (!existing) {
      return write(arguments,list,func(...arguments))
    }
    return existing.value
  }
}
const fibonacci = (n) => {
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
}
let memoFibonacci=memo(fibonacci)
console.log(memoFibonacci(5))

How do I make this higher-order memoization function work for recursive functions?

3 Answers3

Directly define a memoised function

How it looks

Demo

Replace original with memoised

How it looks

Demo

Warnings

Named function expressions

How it looks

Demo

Inner functions

Demo

Modules / other scopes

How it looks