Recursive Generators in JavaScript

Question

I am trying to write a recursive generator for an in order traversal.

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
}

And I am calling the generator like so:

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
}

Why is the generator only yielding 2? Why is it at least not yielding 1 before 2?

How can I fix this?

If it helps, I am transpiling the code using babel.

babel --optional runtime test.js | node

Javascript6 or Ecmascript6? -- http://stackoverflow.com/q/912479/1518921 — Protomen, Sep 25 '15 at 20:08

Amit · Accepted Answer · 2015-09-25T20:38:53.693

64

The problem was not with the recursion. Your function did call itself recursively, it just didn't yield values outside. When you call helper(), you get an iterator as a return value, but you wanted the iterated values of that iterator to be yielded. If you want to yield recursively, you need to yield *. Try like this:

  * 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;
    }
  }

And while you're at it, you can replace the for loop with:

yield * helper(this.root)

edited Sep 25 '15 at 20:38

answered Sep 25 '15 at 20:03

Amit

45,440
9
78
110

Thanks for the answer, it works like a treat. What was happening to cause the function not to recurse? – robbmj Sep 25 '15 at 20:12
1

@robbmj: `helper(node.left);` returns an iterator, but if you don't do anything with the return value, then it it simply lost. You have to consume the iterator somehow. I mean, further down you also do `for (let i of helper(this.root)) {` and not just `helper(node.left);`. It's not any different. – Felix Kling Sep 25 '15 at 20:14
2

The problem was not with the recursion. Your function *did* call itself recursively, it just didn't yield values outside. When you call `helper()`, you get an iterator as a return value, but you wanted the iterated values of that iterator to be yielded, and that's exactly what `yield*` does. – Amit Sep 25 '15 at 20:15
Ahha, okay that makes sense. Thanks again. PS. That comment would be a great addition to your answer. – robbmj Sep 25 '15 at 20:17

score 8 · Answer 2 · answered Oct 22 '15 at 22:42

8

helper(node.left); does call the function and create the generator, but the generator function body is never executed because the generator is never advanced. To forward all of its values to the current generator, you can use the yield* keyword, which works just like the

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

you've used in your inOrderTraversal method. And indeed, that should've been a yield* just as well - or even better, there is no reason to make inOrderTraversal a generator function when it can just be a normal method that returns a generator:

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
}

answered Oct 22 '15 at 22:42

Bergi

630,263
148
957
1,375

"there is no reason to make inOrderTraversal a generator function when it can just be a normal method that returns a generator:" --- One reason is that the function signature declares a generator is being invoked. – Craig Hicks Jul 29 '19 at 06:45
@CraigHicks if you want to declare the signature with TypeScript or Flow, or in the documentation, you'd still use `Generator` as the return type? – Bergi Jul 29 '19 at 10:07
I am aware of but not practically familiar with Typescript and Flow - that comes later. Useful to know that they declare return types ... thanks! – Craig Hicks Jul 30 '19 at 00:15

Recursive Generators in JavaScript

2 Answers2

Linked