How to memoize recursive collatz function with the elements returned in an array?

I have a memoization function that will memoize recursive functions that return a sum, eg Number, but not with my collatz function that returns an array. My map inside the memoization function will have different keys but the same value and does not memoize each step of the function. I am trying to keep this composable as possible.

Console logging inside collatz to check if it's ran will log out the first time as expected.

I have tested this on a exponential recursive function, with a different keymaker function that and it memozies correctly.

const memoized = (fn, keymaker = JSON.stringify) => {
    const lookupTable = new Map();
    return function (...args) {
      const key = keymaker.call(this, args);
      return lookupTable[key] || (lookupTable[key] = fn.apply(this, args));
    }
  };

  const ignoreOthers = ([...values])=>{
    return JSON.stringify(values.shift())
  }


  const memCollatz = memoized((n,arr=[]) =>{
    //console.log('ran')
    if (n<=1) return arr.concat(1)
    else if(n %2 === 0) return memCollatz(n / 2,arr.concat(n))
    else return memCollatz((n*3)+1,arr.concat(n))
  },ignoreOthers)

  console.log(memCollatz(5))
  console.log(memCollatz(6))
  console.log(memCollatz(6))

   
/*
   Map {
    '1': [ 5, 16, 8, 4, 2, 1 ],
    '2': [ 5, 16, 8, 4, 2, 1 ],
    '3': [ 5, 16, 8, 4, 2, 1 ],
    '4': [ 5, 16, 8, 4, 2, 1 ],
    '5': [ 5, 16, 8, 4, 2, 1 ],
    '6': [ 5, 16, 8, 4, 2, 1 ],
    '8': [ 5, 16, 8, 4, 2, 1 ],
    '10': [ 5, 16, 8, 4, 2, 1 ],
    '16': [ 5, 16, 8, 4, 2, 1 ] } 
 */

After running the above console logs this is what my map looks like but should have the n as the key and memoize each step.

Solution

Because of the way you're building up arr inside memCollatz, code execution is going to look like this:

memCollatz(5) | arr = [] | map is empty
memCollatz(16) | arr = [5] | map is empty
memCollatz(8) | arr = [5, 16] | map is empty
memCollatz(4) | arr = [5, 16, 8] | map is empty
memCollatz(2) | arr = [5, 16, 8, 4] | map is empty
memCollatz(1) | arr = [5, 16, 8, 4, 2] | map is empty

That last call to memCollatz(1) is the first to actually return something, so

{1: [5, 16, 8, 4, 2, 1]}

is added to the lookup map

Now, because memCollatz(2) is just returning whatever memCollatz(1) returned, another entry

{2: [5, 16, 8, 4, 2, 1]}

is added to the map

Again, because memCollatz(4) is just returning whatever memCollatz(2) returned, another entry

{4: [5, 16, 8, 4, 2, 1]}

is added to the map

... and so on.

To get around this, you need to avoid this 'pass-through' behaviour, i.e. ensure memCollatz(1) returns something different from memCollatz(2), etc.

Here's an example:

  const memCollatz = memoized((n) =>{
    if (n<=1) return [1];
    else if(n %2 === 0) return [n].concat(memCollatz(n / 2))
    else return [n].concat(memCollatz((n*3)+1))
  },ignoreOthers)