I recently solved the basic problem of generating a n-bit Gray Code. The solution I used involved building larger-bit Gray Codes from smaller ones recursively (the solution I've seen on most websites).
However, I then had an idea for a Greedy Gray Code Algorithm: Start the Gray Code at 0 and at every step, find and change the single smallest bit such that we get a new, not-visited-before number. Keep on repeating this until we have exhausted all the
2^N possible numbers with
I was sure that this approach wouldn't work for some values of
N, but so far, it has worked for all
N from 1 to 30. This was quite surprising for me, especially as I haven't seen this Greedy approach mentioned anywhere as a solution to the Gray Code Problem.
So, my question is, does this Greedy algorithm for generating N-bit Gray Codes always work? Is there a proof of its correctness? Otherwise, what value of
N causes this algorithm to not be able to generate a correct Gray Code?