How can I simplify this generator to eliminate the recursion?

I’m trying to create a generator that yields values between a given range. My requirements are:

• all emitted values are unique
• the order of values is the same every time the generator is run
• each value is far away from previously emitted values
• it is not known how many values will be generated

I’ve decided to model this as a tree, and doing something like a breadth first search to split the range up into even sized subdivisions, and iterating over each layer in an order that avoids adjacent node visiting.

I’ve come up with the following solution which works, however I don’t like that it is using recursion, and I suspect it can be rewritten to eliminate the recursion (maybe a queue?) A bit stuck here. Here’s what I have so far:

function* orderedSubdivisor(start: number, end: number): Generator<number> {

    const mid = (end - start) / 2 + start
    
    yield mid

    const left = orderedSubdivisor(start, mid)
    const right = orderedSubdivisor(mid, end)

    while (true) {
      yield left.next().value
      yield right.next().value  
    }
}

const iter = orderedSubdivisor(0, 64)

console.log(Array.from({length: 63}, () => iter.next().value))

thanks!

Answer

You can model this using a binary counter to represent the position/path in your tree. The least significant bit decides whether you are in the left or right half of the top branch, the second-least significant bit decides whether you are in the left or right half on the second level, and so on:

function* orderedSubdivisor(start, end) {
    for (let i=1; true; i++) {
        let sum = start;
        let part = end-start;
        for (let j=i; j; j=j>>>1) {
            part /= 2;
            if (j & 1) sum += part;
        }
        yield sum;
    }
}

const iter = orderedSubdivisor(0, 64)

console.log(Array.from({length: 63}, () => iter.next().value))

In fact you can see that you’ve essentially just created a counter, but flip the bit order of every yielded value:

function* orderedSubdivisor(start, end) {
  const mid = (end - start) / 2 + start
  yield mid
  const left = orderedSubdivisor(start, mid)
  const right = orderedSubdivisor(mid, end)
  while (true) {
    yield left.next().value
    yield right.next().value  
  }
}

let i=0;
for (const v of orderedSubdivisor(0, 64)) {
  if (i++ >= 63) break;
  document.body.appendChild(document.createElement('pre')).textContent = v.toString(10).padStart(2)+': 0b'+v.toString(2).padStart(6, '0');
}