Implement a function that generates a Gray code. A Gray code is a sequence of numbers from $0$ to $2^n - 1$ such that only one bit changes between successive numbers.

For example, the following is a Gray code for $n = 4$:

             0    0000
             1    0001
             3    0011
             2    0010
             6    0110
             7    0111
             5    0101
             4    0100
            12    1100
            13    1101
            15    1111
            14    1110
            10    1010
            11    1011
             9    1001
             8    1000

You will note that one way of generating a Gray code for $n = 4$ is to generate a Gray code for $n = 3$:

             0     000
             1     001
             3     011
             2     010
             6     110
             7     111
             5     101
             4     100

append to this the same list, but in reverse order:

             0     000
             1     001
             3     011
             2     010
             6     110
             7     111
             5     101
             4     100
             4     100
             5     101
             7     111
             6     110
             2     010
             3     011
             1     001
             0     000

and to then prepend the first half with a 0 bit and the second half with a 1 bit (that is, add 8):

             0    0000
             1    0001
             3    0011
             2    0010
             6    0110
             7    0111
             5    0101
             4    0100
         8 + 4    1100
         8 + 5    1101
         8 + 7    1111
         8 + 6    1110
         8 + 2    1010
         8 + 3    1011
         8 + 1    1001
         8 + 0    1000

As you will note, because the gray code with three bits is a gray code, the differences between the first eight and the last eight is exactly one bit. Then, between the first eight and the second eight, only the first bit changes.

You will write two functions

unsigned long *gray_code( unsigned int n );
void gray_code_print( unsigned int n );

The first returns a dynamically-allocated array of capacity one containing the entry $0$ if $n = 0$ and a dynamically-allocated array of capacity two containing the entries $0$ and $1$ if $n = 1$. For $n \geq 2$, the function will recursively call gray_code( n - 1 ), take the returned array and use this to construct a dynamically allocated array of capacity $2^n$ by using the approach described above. Your function must then delete the dynamically allocated array returned by the function call gray_code( n - 1 ) before returning the array of capacity $2^n$.

The second simply calls the first, prints the output (one code per line) and the deletes the returned array.

References

Wikipedia