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

Answer 1

问题不在于递归。您的函数 did 递归调用自身，它只是没有在外部产生值。当您调用 helper() 时，您将获得一个迭代器作为 return 值，但您希望生成该迭代器的迭代值。如果你想递归地产生，你需要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* keyword，它的工作方式与

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

您在 inOrderTraversal 方法中使用过。事实上，这也应该是一个 yield* - 甚至更好，没有理由让 inOrderTraversal 成为一个生成器函数，因为它可以只是一个 returns 的普通方法发电机：

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
}

JavaScript 中的递归生成器

Recursive Generators in JavaScript

javascript

recursion

generator

ecmascript-6