Рекурсивные генераторы в JavaScript

Я пытаюсь написать рекурсивный генератор для обхода.

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

Ответ 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)

Ответ 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
}