Building a range generator in JavaScript – Part II

We did a for loop based range generator.
How about doing range generator without for loop?

Well, usually eliminating for loop can be done by converting the function to a recursive one.

Iterative approach, using a for loop

function factorial(num) {
  let f = 1;

  for (let value=1; value<=num; value++)
    f *= value;

  return f;
}

Converted to recursive (eliminate for)

function factorial(num) {
   if (num < 1)
      return 1;
   return num * factorial(num - 1);
}

See! For loop gone!!

We can perhaps do the same thing with our for-loop based generator too.

Let's take this for based generator

function* range(start, end, skip) {

  // If end not provided, assume 0..start
  end == undefined && ([end, start] = [start, 0]);

  // Check order and set skip, if needed
  let ascending = start < end;

  if (ascending && skip <= 0 ||
    !ascending && skip >= 0)
    return null;

  !skip && (skip = ascending ? +1 : -1);

  // Set which direction we want to skip
  const condition =
    ascending
      ? ((value, end) => value < end)
      : ((value, end) => value > end);

  // Now 'yield' values in a loop
  for (var value = start;
    condition(value, end);
    value += skip)
    yield value;
}

And convert it into recursion based

But how?

JavaScript uses yield to generate a value, but it also has yield * to invoke a function or a source of values to generate individual yields

function* pie() {
  yield* [3, 1, 4, 1, 5, 2, 9];
}

for (let digit of pie)
  console.log(digit);
// 3, 1, 4, 1, 5, 2, 9

We can also apply yield* to a function, like this

function* realGenerator(num) {
  for (let value = 0;
       value < num;
       value++) {

    yield value;
  }
}

function* generator() {
  yield *realGenerator(5);
}

console.log([...generator()]);

So yield* can apply to other generators and return us a stream of values.. hmmm.

What if we applied yield* to our own function? Yeah! Recursively!

function* natural(num) {
  if (num > 1)
    yield* natural(num - 1);
  yield num;

}

console.log([...natural(5)]);

The above code prints a list of natural numbers by recursively calling itself and yielding on natural number at a time. See! No for-loop.

We are READY!

function* range(start, end, skip) {
  
  // Sanity checks
  if ((start == undefined) ||
    (start != undefined 
      && end == undefined && skip != undefined) ||
    (start < end && skip <= 0) ||
    start > end && skip >= 0)
    return null;

  // Check for situations like range(5) and make it range(0, 5)
  end == undefined && 
    ([end, start] = [start, 0]);

  // If skip is undefined, set it to +1 or -1 depending on range
  !skip && (skip = (start < end) ? +1 : -1);

  // While recursing, have we hit the end?
  if (start != end) {
    recursing = true;

    // THERE! We are using recursion
    yield* range(start, end - skip, skip);
    yield end - skip;
  }
}

However, this is wasteful. With every recursion we are doing sanity checks, end check, skip check, which should be done only once. We can put debug statements to follow the flow.

debug = console.log;
function* range(start, end, skip) {
  debug(`Called for ${start}, ${end}, ${skip}`);

  // Sanity checks
  if ((start == undefined) ||
    (start != undefined && end == undefined && skip != undefined) ||
    (start < end && skip <= 0) ||
    start > end && skip >= 0)
    return null;

  // Check for situations like range(5) and make it range(0, 5)
  end == undefined && ([end, start] = [start, 0]);

  // If skip is undefined, set it to +1 or -1 depending on range
  !skip && (skip = (start < end) ? +1 : -1);

  // While recursing, have we hit the end?
  if (start != end) {
    recursing = true;
    yield* range(start, end - skip, skip);
    yield end - skip;
  }
}

// Should print 10, 8, 6, 4, 2
console.log("range(10, 0, -2): ", [...range(10, 0, -2)]);

And here is the output

Called for 10, 0, -2
Called for 10, 2, -2
Called for 10, 4, -2
Called for 10, 6, -2
Called for 10, 8, -2
Called for 10, 10, -2
range(10, 0, -2):  [ 10, 8, 6, 4, 2 ]

As we can see, when we recursively call the function for yield, it goes thru all the checks all over again, which it should do only once.

Hmm! How do we avoid it? IDEA! Closure.
We can decalre a closure variable ‘recursing’ and set it to false. When we call the function the first time, it will be false and we can do all the checks. However, upon recursion, we will set it to true and skip all the check. Neat!

var recursing = false;
const nop = (...rest) => { };
let debug = console.log;

function* range(start, end, skip) {

  // Change to tru to see unnecessary recursion
  if (!recursing) {
    debug(`Called for ${start}, ${end}, ${skip}`);

    // Sanity checks
    if ((start == undefined) ||
      (start != undefined && 
        end == undefined && skip!= undefined) ||
      (start < end && skip <= 0) ||
      start > end && skip >= 0)
      return null;

    // Check for situations like range(5)
    // and make it range(0, 5)
    end == undefined && 
      ([end, start] = [start, 0]);

    // If skip is undefined, 
    // set it to +1 or -1 depending on range
    !skip && (skip = (start < end) ? +1 : -1);
  }

  // While recursing, have we hit the end?
  if (start != end) {
    recursing = true;
    yield* range(start, end - skip, skip);
    yield end - skip;
  }
  recursing = false;
}

// Remove this line to see debug prints
debug = nop;

// Should print [ 0, 1, 2, 3, 4 ]
console.log("range(5): ",  [...range(5)]);

What's the output now?

Called for 10, 0, -2
range(10, 0, -2):  [ 10, 8, 6, 4, 2 ]

Yep! We have an optimised recursion based range generator, which works asc/desc. with any value for skip.
However, recursion is an expensive proposition. It creates a new stack frame for every recursive call and always has the danger of running out of stack space, resulting in StackOverflow.

I tend to prefer iterative solutions over recursive ones, unless recursive leads to elegant code.

So, the next blog? Iterative range generator – WITHOUT recursion and WITHOUT for-loop