I need to implement a recursive code for generating the Gray code for a given number of bits. For example, if the input bit is 1 it generates Gray code for 1 bit number i.e 0 and 1. Given 2, it generates Gray code for 2 bit numbers i.e 00 and 01 and so on. I don't understand how to implement and what should be the base case.
First, a few pointers about recursion:
- Find the base case
- Implement that first
- Define when you should go in recursion
- If the recursive call succeeds once, it will always succeed
As you may know, recursion is, essentially, solving a huge problem by solving the smaller parts of the problem which are, in essence, the same problem as the huge one. The postulate is that when all smaller problems have been solved, the problem as a whole has been solved.
Anyway, enough of that.
Your base case is 1 bit, which results in G = {0,1}. To go to n = 2, reflect the bits (it becomes {1,0}), concatenate that list with the original list and append the 0 to the original list and the 1 to the reflected list, resulting in G = {{00},{01},{11},{10}}.
n = 1
0
1
Reflect and concatenate:
0
1
1
0
Append zeros and ones:
00
01
11
10
We now have n = 2.
In short, you pass a number of bits to your method, n that specifies the Grey code for n bits. Recursively go down to one, where you can create the base for n = 1, then work your way back up.
Code:
char[] bits
void grayCode(int numBits) {
if(bits == 1) {
bits = ['0','1'];
} else {
if(numBits != 1) {
grayCode(numBits - 1);
}
char[] mirroredBits = reverse(bits);
bits.concat(mirroredBits);
//for the first n bits, append 0
//for the last n bits, append 1
}
}
Okay, it's ugly and not C, but I'm sure you can translate it to proper C which will output exactly what you need. This code goes down to your base case, constructs it and then expands upon the base case until the specified number of bits has been reached.