Introduction

Generators and Iterators enable lazy evaluation in JavaScript. Used in a loop, for example, executions "pauses" at each yield statement until the next iteration is requested. What is often overlooked is that generators can be recursive functions. In this brief article, I'll go over a simple example that demonstrates how one can create a recursive generator function for lazy evaluation.

Yield

Most documentation on generators provide iterative examples, often using a while or for construct with a yield statement. For example, a simple generator that yields sequential numbers could be written like this:

function* count() {
  let count = 0
  while( true ) {
    yield count++
  }
}

Iteration is fine; but what about algorithms that are better expressed recursively? How can we use generators to create lazily evaluated recursive functions? We do this by delegating to another generator.

The yield* keyword (with asterisk)

Meet yield*, the lazier cousin of the yield statement. The yield statement pauses with the next value until requested. On the other hand, the yield* statement (with an asterisk) simply defers to another iterator object.

Evaluation doesn't actually stop at yield*, it is merely a syntax to indicate that we'll forward all yields from the given iterator object until it finishes--after which we resume. It turns out, this is quite powerful.

For our first example, let's suppose we want to loop over an iterable, endlessly. We could do this as follows:

function* loop( iterable ) {
  yield* iterable
  yield* loop( iterable )
}

For our second example, we'll look at a more concrete scenario--here is a function that generates array permutations using Heap's Permutation algorithm:

function* heapsPermutationsMutating( source, end = source.length  ) {
  // base case
  if( end === 1 ) { yield [ ... source ] }

  // branch
  for ( var index = 0; index < end; index++ ) {
    yield* heapsPermutationsMutating( source, end - 1 );
    swap( source, end - 1, end % 2 === 0 ? index : 0 )
  }
}

function* heapsPermutations( source ) {
  yield*  heapsPermutationsMutating( source )
}

function swap( arr, i1, i2 ) {
  return [ arr[ i1 ], arr[ i2 ] ] = [ arr[ i2 ], arr[ i1 ] ] 
}

Notice that we don't need to build and keep the resulting array because we yield each permutation and move on. The yield* keyword defers to the yield given in the base case reached at the end of each recursive branch.

This pattern works great for many recursive solutions. What makes the approach great in terms of space and time complexity is that we can stop execution after we get our desired result--we don't need to generate all permutations.

To illustrate this, here is a take generator function that we can use to only create a specific number of permutations.

function* take( num, iter ) {
  let item = iter.next()
  for( let index = 0; index < num && !item.done ; index++) {
    yield item.value
    item = iter.next()
  }
}

To take just the first 5 permutations of an array, we might do something like this:

let permutate5 = [ ...take( 5, heapsPermutations([1,2,3,4,5]) ) ]

Conclusion

Recursive lazy evaluation further improves JavaScript's functional capabilities. It shouldn't be overlooked! Many algorithms are expressed much more elegantly and naturally when written recursively. Recursive functions are just as capable of lazy evaluation as their iterative counterparts.