Skip to content
Advertisement

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:

JavaScript

thanks!

Advertisement

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:

JavaScript

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

JavaScript
User contributions licensed under: CC BY-SA
6 People found this is helpful
Advertisement