# Python Program to Generate Gray Codes using Recursion

This is a Python program to generate all gray codes using recursion

Problem Description

The number of bits n is given. The problem is to generate the n-bit Gray code. The Gray code is an ordering of the binary numbers such that two successive codewords differ in only one bit.

Problem Solution

1. The function get_gray_codes is defined.
2. It takes the number of bits n as argument.
3. It returns n-bit Gray code in a list.
4. The function works by first obtaining the (n – 1)-bit Gray code.
5. The first half of the n-bit Gray codewords are simply the (n – 1)-bit Gray codewords prepended by a 0.
6. The second half of the n-bit Gray codewords are (n – 1)-bit Gray codewords listed in reverse and prepended with a 1.
7. The 0-bit Gray code simply consists of the empty string.

Program/Source Code

Here is the source code of a Python program to generate all gray codes using recursion. The program output is shown below.

```def get_gray_codes(n):
"""Return n-bit Gray code in a list."""
if n == 0:
return ['']
first_half = get_gray_codes(n - 1)
second_half = first_half.copy()

first_half = ['0' + code for code in first_half]
second_half = ['1' + code for code in reversed(second_half)]

return first_half + second_half

n = int(input('Enter the number of bits: '))
codes = get_gray_codes(n)
print('All {}-bit Gray Codes:'.format(n))
print(codes)```
Program Explanation

1. The user is prompted to enter the number of bits.
2. get_gray_codes is called on the number of bits.
3. The returned list is displayed.

Runtime Test Cases
```Case 1:
Enter the number of bits: 3
All 3-bit Gray Codes:
['000', '001', '011', '010', '110', '111', '101', '100']

Case 2:
Enter the number of bits: 1
All 1-bit Gray Codes:
['0', '1']

Case 3:
Enter the number of bits: 4
All 4-bit Gray Codes:
['0000', '0001', '0011', '0010', '0110', '0111', '0101', '0100', '1100', '1101', '1111', '1110', '1010', '1011', '1001', '1000']```

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.

Note: Join free Sanfoundry classes at Telegram or Youtube

If you find any mistake above, kindly email to [email protected]