Take n = 3 as an example:

(xxx are in binary representation):

Base case n = 1

000

001

Add bits 10 backward to the above 2 results

011

010

Add bits 100 backward to the above 4 results

110

111

101

100

```
def grayCode(self, n):
if n < 1:
return [0]
elif n == 1:
return [0, 1]
else:
result = self.grayCode(n - 1)
mostSignificantBit = 1 << (n - 1)
prevResultSize = len(result)
for i in range(prevResultSize - 1, -1, -1):
result.append(mostSignificantBit + result[i])
return result
```