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.