尾递归归约函数 returns [..., [Circular] ]

Question

正在尝试编写一个可以过滤掉任何重复项的 reduce 函数。我知道还有其他方法可以解决这个问题，但我正在尝试练习递归函数。

function addToSet(a, b) {
  a.add(b);
  return a;
}

let set = new Set;

function reduce([head, ...last], fn, init) {
  if (head === undefined) return init;
  return fn(fn(init, head), reduce(last, fn, init))
}
const a = reduce([1, 2, 4, 6, 4, 3, 1, 2, 5, 1, 3, 4, 5, 7, 7], addToSet, set)

console.log(a)

// in node this returns // Set { 1, 2, 4, 6, 3, 5, 7, [Circular] }

我读到那个通告意味着对象是自引用的？但我不确定我是否完全理解这在 Set 的上下文中意味着什么。为什么我会遇到这个问题，我该如何解决？非常感谢你们的宝贵时间！

Answer 1

为了弄清楚这里发生了什么，我们可以在您的递归函数中放置一个控制台日志，然后运行它有一个像这样的小集合：

function addToSet(a, b) {
  a.add(b);
  return a;
}

let set = new Set;

function reduce([head, ...last], fn, init) {
  console.log("head", head)
  console.log("last", last)
  console.log("init", init)
  if (head === undefined) return init;
  return fn(fn(init, head), reduce(last, fn, init))
}
const a = reduce([2, 4, 4], addToSet, set)

console.log(a)

我们得到了这个输出（记住最后一行是 return 来自最后初始调用的内容）

如您所见，您最后一次在空数组上调用了递归函数并在那里 return init，它被添加到集合的末尾。您可能想通过修改基本案例来抓住这一点。我会把它作为练习留给你去弄清楚，但如果你需要更多帮助，你可以随时回复。

再想想：

考虑递归就像说函数的一个运行将负责一个 action/calculation/step/however 你想考虑的函数。问问自己那一步是什么。

例如：

如果我是一个函数调用，也许我只想对问题负责"do I add the current head to init?"

有很多方法可以做到这一点，但也许一种方法是（用伪代码）：

reduce([head, ...last], fn, init) {
  is_base_case (where head is undefined)?
    return // do nothing -- we don't want undefined to be in the set
  otherwise
    attempt to add head to init
  reduce(...) // call the next reduce fn -- responsible for the next head
  return init // init should either have the original set or the set + head
}

这并没有说明 undefined 实际上是数组中的一个值，但希望它能说明这个概念。

Answer 2

考虑这一点的一个好方法是只查看 addToSet 的 return 值。它 return 是传入的集合……每次。现在查看 reduce 的 return 值。它 return 是我们刚刚建立的 fn 的结果总是 return 集合。

所以你将 reduce 的结果传递到 fn 的第二个参数中，在某些时候你会将集合传递到第二个参数 fn 中，这将添加集合到集合并给你一个循环参考。

这个：

 return fn(fn(init, head), reduce(last, fn, init))

最终变成：

 return fn(init, init)

不难解决，因为没有真正的理由让函数调用两次。您的基本情况将 return 最后设置，因此您只需调用 fn 一次， return reduce.

的结果

function addToSet(a, b) {
    a.add(b);
  }
  
  let set = new Set;
  
  function reduce([head, ...last], fn, init) {
    if (head === undefined) return init
    fn(init, head)
    return reduce(last, fn, init)
  }
  const a = reduce([1, 2, 4, 6, 4, 3, 1, 2, 5, 1, 3, 4, 5, 7, 7], addToSet, set)
  
 console.log([...a]) // spreading because sets don't print here

尾递归归约函数 returns [..., [Circular] ]

Tail recursive reduce function returns [..., [Curcular] ]

javascript

recursion

function

circular-reference

node.js