Using recursion to find all gray codes with n bits

1. Let's first look at what gray code is

Gray Code It's a sequence set , Each number is represented in binary , Suppose you use n Bits to represent each number , Then there is only one bit value different between any two numbers .

log2(16)=4 for example ： Generate 4 The gray code of bits is ： 0000 0001 0011 0010 0110
0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000
G

ray Code The order of is not unique , It can be any one of the sequence formed by the above .Gray Code By Bell Laboratories Frank Gray stay 1940 Proposed in the S , Used in use PCM（Pusle Code Modulation） Method to avoid errors when transmitting signals , And in 1953 On March 17, 2004, it obtained a U.S. patent . If you want to produce n Bit gray code , Then the number of gray codes is 2^n individual

2. Must be able to write test questions

problem ： Use recursion to solve n Bit all gray codes

Problem solving skills ：

We may have been startled by the question as soon as we came up , I think this is a very difficult problem ,

When we calmly analyze ：

1 Bit code ：
0
1

2 Bit code
00
01
11
10

3 Bit code

000
001
011
010
110
111
101
100

It's not hard to find out ：
2 The bit gray code is composed of 1 The bit gray code is preceded by 0 and 1, And all bits except the first are symmetric
3 The bit gray code is composed of 2 The bit gray code is preceded by 0 and 1, And all bits except the first are symmetric
So you can use recursion ：
n Bit code [ i ] = “0” + n-1 Bit code [ i ]
n Bit code [2^n-i-1]=“1”+n-1 Bit code [ i ]

So the code is written :

public String[] getGray(int n) {
    
// Define an array to hold the results , The size is 2 Of n Power 
   String[] strs = new String[(int)Math.pow(2,n)];
   if(n == 1){
     // If n by 1, Directly assign the value and return the result 
       strs[0] = "0";
       strs[1] = "1";
       return strs;
   }
   // If not for 1, Start recursive logic , seek n First of all n-1, seek n-1 First of all n-2,..... Final recursion to 1, Start back to , The final result n
   // Each recursive process will use the following loop to prefix the gray code of the previous bit with 0 Add 1, Get the gray code required this time 
   String[] str = getGray(n-1);
    for (int i = 0; i < str.length; i++) {
    
        strs[i] = "0" + str[i];
        strs[strs.length-i-1] = "1" + str[i];
    }
    return  strs;
}