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))
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]

Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.