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.
Top comments (1)
nice!! very nice!!
I would add:
function* take( num, iter ) {
let item = iter.next()
for( let index = 0; index < num && !item.done ; index++) {
yield item.value
item = iter.next()
}
iter.return() // <--
}
so that the generator is resumed after the for finished else it would never finish