Iteration Explained

The Iteration class converts recursive algorithms into iterative streams.

If you've needed to create iterators (or streams) for recursive algorithms, you might agree that it's feasible but requires some careful manual stack manipulation to get it right. The code tends to be less than intuitive.

The Iteration class attempts to solve this kind of problem in a generic way. Let's look at a few examples.

Fibonacci Stream

The Fibonacci is an infinite sequence of numbers where the current element is the sum of the previous two elements. If you need to create a lazy stream of Fibonacci numbers, this is what you could do:

class Fibonacci extends Iteration<Long> {
  Fibonacci from(long a, long b) {
    // `yield` is becoming a keyword in Java 21+, so use `this.`
    this.yield(a);                    // current element
    this.yield(() -> from(b, a + b)); // the recursion
    return this;                      // for chaining
  }
}

new Fibonacci()
    .from(0, 1)
    .iterate()
    .limit(20)
    .forEachOrdered(System.out:println);

Post-order binary tree traversal

You could have the post-order traversal hard-coded like this:

void printNodesInPostOrder(Tree<N> tree) {
  if (tree.left != null) {
    printNodesInPostOrder(tree.left);
  }
  if (tree.right != null) {
    printNodesInPostOrder(tree.right);
  }
  println(tree.node);
}

It's simple but not very flexible. Using the Iteration class, you can trivially turn it into a Stream of nodes. All you need is to wrap the recursion calls in this.yield(), and also replace the println() with this.yield():

class PostOrder extends Iteration<N> {
  static <N> Stream<N> postOrderFrom(Tree<N> tree) {
    rerturn new PostOrder<N>().visit(tree).iterate();
  }

  private PostOrder visit(Tree<N> tree) {
    if (tree.left != null) {
      this.yield(() -> visit(tree.left);
    }
    if (tree.right != null) {
      this.yield(() -> visit(tree.right);
    }
    this.yield(tree.node);
    return this;
  }
}

Again, the streams is fully lazy.