Python Program to Generate Gray Codes using Recursion

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

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.

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.

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)

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.

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.