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？为什么它至少没有产生1之前2？

我怎样才能解决这个问题？

如果它有帮助,我正在使用babel来编译代码.

babel --optional runtime test.js | node

Answer 1

问题不在于递归.你的函数确实递归地调用了它,它只是没有在外面产生值.当你调用helper()时,你得到一个迭代器作为返回值,但是你想要得到迭代器的迭代值.如果你想递归地屈服,你需要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)

Answer 2

helper(node.left);确实调用了函数并创建了生成器，但是生成器函数体永远不会执行，因为生成器永远不会被推进。要将其所有值转发到当前生成器，您可以使用yield*关键字，其工作方式与

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

你在你的inOrderTraversal方法中使用过。事实上，这也应该是一个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
}