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

Question

我有一个记忆函数，可以记忆 return 一个总和的递归函数，例如 Number，但不能用我的 return 数组的 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

由于您在 memCollatz 中构建 arr 的方式，代码执行将如下所示：

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) 的最后一次调用实际上是第一个 return 东西，所以

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

添加到查找映射

现在，因为 memCollatz(2) 只是 returning 任何 memCollatz(1) returned，另一个条目

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

已添加到地图

同样，因为 memCollatz(4) 只是 returning 任何 memCollatz(2) returned，另一个条目

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

已添加到地图

...等等。

要解决这个问题，您需要避免这种 'pass-through' 行为，即确保 memCollatz(1) returns 与 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)

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

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

javascript

recursion

memoization

如何使用数组中返回的元素记忆递归 collat​​z 函数？

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

javascript

recursion

memoization

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