JavaScript中的递归生成器

Question

我试图编写一个用于中序遍历的递归生成器。

我试图编写一个用于中序遍历的递归生成器。

class Tree {
  *inOrderTraversal() {
    function* helper(node) {
      if (node.left !== null) {
        // this line is executed, but helper is not being called
        helper(node.left); 
      }
      yield node.value;
      if (node.right !== null) {
        helper(node.right);
      }
    }

    for (let i of helper(this.root)) {
      yield i;
    }
  }
  // other methods omitted
}

我这样调用生成器：

const tree = new Tree();
tree.add(2);
tree.add(1);
tree.add(3);

for (let i of tree.inOrderTraversal()) {
    console.log(i); // only prints 2
}

为什么生成器仅产生2？至少为什么在2之前不会产生1？

如何修复它？

如果有帮助的话，我正在使用Babel转译代码。 babel --optional runtime test.js | node

- robbmj

---

Javascript6还是Ecmascript6？-- https://dev59.com/tnNA5IYBdhLWcg3wjOve - Guilherme Nascimento

Answer 1

问题并不在于递归。您的函数确实会递归调用自己，只是没有产生外部值。当您调用helper()时，您会得到一个迭代器作为返回值，但您希望该迭代器的迭代值被产生。如果您想要递归产生yield值，您需要使用yield *。尝试像这样：

  * inOrderTraversal() {
    function* helper(node) {
      if (node.left !== null) {
        // this line is executed, but helper is not being called
        yield * helper(node.left); 
      }
      yield node.value;
      if (node.right !== null) {
        yield * helper(node.right);
      }
    }

    for (let i of helper(this.root)) {
      yield i;
    }
  }

同时，在进行这个操作的过程中，你可以将 for 循环替换为：

yield * helper(this.root)

- Amit

---

感谢您的答案，它确实很有效。是什么原因导致函数无法递归？ - robbmj

@robbmj: helper(node.left); 返回一个迭代器，但如果你不对返回值做任何操作，那么它就会被简单地丢失。你必须以某种方式消耗这个迭代器。我的意思是，往下你也要做 for (let i of helper(this.root)) { 而不仅仅是 helper(node.left);。这没有任何区别。 - Felix Kling

问题并不在于递归。你的函数确实会递归调用自己，只是没有产生外部值。当你调用 helper() 时，会得到一个迭代器作为返回值，但你想要迭代该迭代器的值被产生，这正是 yield* 所做的事情。 - Amit

啊哈，好的，那很有道理。再次感谢。附言：那个评论会是你回答的一个很好的补充。 - robbmj

Answer 2

helper(node.left);会调用该函数并创建生成器，但是由于生成器从未被推进，因此生成器函数体也从未被执行。要将所有值转发给当前生成器，您可以使用yield*关键字，它的工作方式与所述类似。

for (let i of helper(this.root))
    yield i;

在您的inOrderTraversal方法中使用了yield，实际上，这也应该是一个yield* - 或者更好的是，没有必要将inOrderTraversal设置为生成器函数，因为它可以只是一个返回生成器的普通方法：

class Tree {
  inOrderTraversal() {
    function* helper(node) {
      if (node.left !== null)
        yield* helper(node.left);
      yield node.value;
      if (node.right !== null)
        yield* helper(node.right);
    }

    return helper(this.root);
  }
  … // other methods
}

- Bergi

---

没有理由将inOrderTraversal制作为生成器函数，因为它可以只是一个返回生成器的普通方法。但有一个原因就是函数签名声明了正在调用一个生成器。 - Craig Hicks

@CraigHicks 如果你想用TypeScript或Flow声明签名，或者在文档中，你仍然会使用Generator作为返回类型吗？ - Bergi

我知道TypeScript和Flow，但实际上并不熟悉它们 - 这将在以后进行。了解它们声明返回类型很有用...谢谢！ - Craig Hicks