July 7, 2020 – Digital Concept Visuals

Well, in the last posts we covered how to write a range generator function using for-loop and recursion. While iterative algorithms are more efficient because they do not create additional stack frames and pass data across function calls, however, in these times of functional programming, imperative programming is getting less popular.

So how do we create iterative and yet not recursive algorithm to generate range() in JavaScript?

Array method and spread magic

function generate(size) {

  // Create an empty array 
  let empty = new Array(size);

  // It contains 5 empty slots
  console.log(empty);

  // Now create a filled array
  // Use empty array's offset
  let filled = [...empty.keys()];

  // [0, 1, 2, 3, 4 ]
  console.log(filled);
}

generate(5);

Output?

empty [ <5 empty items> ]
filled [ 0, 1, 2, 3, 4 ]

Hey! We have already generated a range(5) of 0..4. Why not take this further and make it flexible?

We are getting closer

function generate(size, skip=1) {

  // Create an empty array 
  let empty = new Array(size);

  // It contains 5 empty slots
  console.log("empty", empty);

  // Now create a filled array
  // Use empty array's offset
  let filled = [...empty.keys()];

  // [0, 1, 2, 3, 4 ]
  console.log("filled", filled);

  // Range with skip
  
  let ready = [...empty.keys()]
    .map(value => value * skip);
  console.log("ready", ready);
}

generate(5, 2);

Output

empty [ <5 empty items> ]
filled [ 0, 1, 2, 3, 4 ]
ready [ 0, 2, 4, 6, 8 ]

So now we can generate an array of specific size, fill it with values and those values can come from an expression like value * skip

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);

  yield* [...
    [...Array(Math.abs(end - start) 
       / Math.abs(skip)).keys()]
      .map(value => start + value * skip)
  ];
}

Woah! What happened!!!

Nothing much.. just two things
1. Generate an array of given size e.g.
range(5) -> array of 5 (0, 1, 2, 3, 4)
range(0, 3) -> array of 3 (0, 1, 2)
range(0, 6, 2) -> array of 3 (0, 2, 4) we are skipping 2!

// Generate array of start to end / skip
[...Array(Math.abs(end - start) / Math.abs(skip)).keys()]

But the above array is empty, so we are using keys(), which will only give us 0, 1, 2, 3…
It won’t apply skip if its other than 1.

2. Fill the array with values
range(0, 6, 2) should generate (0, 2, 4)

Ascending with skip

// generate(3, 8, 2) -> (3, 5, 7)
.map(value => start + value * skip)
// 0 => 3 + 0 * 2 == 3
// 1 => 3 + 1 * 2 == 5
// 2 => 3 + 2 * 2 == 7

Descending

// generate(6, 0, -2) -> (6, 4, 2)
.map(value => start + value * skip)
// 0 => 6 + 0 * -2 == 6
// 1 => 6 + 1 * -2 == 4
// 2 => 6 + 2 * -2 == 2

.map() is so sweet! It transform our offsets into final values.

// Yield values from the array
// Where were generate array with keys
// Then map the offsets into range values
yield* [...
    [...Array(Math.abs(end - start) 
        / Math.abs(skip)).keys()]
      .map(value => start + value * skip)
  ];

So there we have it. An iterative range generator function which does not us any form of imperative statements like if and for and is more efficient than a recursive range generator.

If you know another way of generating range function, do post a comment!

Range Generator Series

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