Как запомнить рекурсивную функцию collatz с элементами, возвращаемыми в массиве?

Question

У меня есть функция памятки, которая запоминает рекурсивные функции, которые возвращают сумму, например, Number, но не с моей функцией collatz, которая возвращает массив.Моя карта внутри функции запоминания будет иметь разные ключи, но одно и то же значение, и не будет запоминать каждый шаг функции.Я пытаюсь сохранить эту возможность компоновки настолько, насколько это возможно.

Запись в консоль внутри collatz, чтобы проверить, будет ли она запущена, выйдет из системы в первый раз, как и ожидалось.

Я проверил это на экспоненциальной рекурсивной функции с другой функцией keymaker, которая правильно запоминает.

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 ] } 
 */

После запуска вышеприведенных журналов консоли это то, на что похожа моя карта, но должна иметь n в качестве ключа и запоминать каждый шаг.

Answer 1

Из-за того, как вы создаете arr внутри memCollatz, выполнение кода будет выглядеть так:

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

Этот последний вызов memCollatz (1) является первым, который фактически возвращаетчто-то, так что

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

добавлено к карте поиска

Теперь, потому что memCollatz (2) просто возвращает то, что memCollatz (1) вернул, еще одна запись

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

добавлено на карту

Снова, потому что memCollatz (4) просто возвращает то, что memCollatz (2) вернул, другая запись

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

добавлено на карту

... и т. Д.

Чтобы обойти это, вам нужно избегать такого «сквозного» поведения,т.е. убедитесь, что memCollatz (1) возвращает что-то отличное от memCollatz (2) и т. д.

Вот пример:

  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)