如何用数组中返回的元素回溯递归collatz函数？

Question

我有一个回忆录函数，它将回溯返回和(例如数字)的递归函数，但与返回数组的collatz函数不同。我的地图内回忆录功能将有不同的键，但相同的价值，并没有回忆录的每一步的功能。我正试着让这个合成尽可能好。

在collatz中进行控制台日志记录，以检查它是否已运行，第一次将按预期的方式注销。

我在一个指数型递归函数上测试了这一点，使用了一个不同的键制造者函数，它正确地记住了这个函数。

​

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

由于您在memCollatz中构建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)