Python Program to Generate Gray Codes using Recursion

In this Python program, we will generate Gray codes using recursion. Gray code is a binary numeral system where two successive values differ by only one bit. It is often used in various applications, such as digital communications and error correction.

Problem Statement

Given a positive integer n, we need to generate the Gray codes of length n using recursion.

Python Program to Generate Gray Codes using Recursion

def generate_gray_codes(n):
    if n == 1:
        return ['0', '1']
    
    prev_gray_codes = generate_gray_codes(n - 1)
    gray_codes = []
    
    for code in prev_gray_codes:
        gray_codes.append('0' + code)
    
    for code in reversed(prev_gray_codes):
        gray_codes.append('1' + code)
    
    return gray_codes


# Test the program
n = int(input("Enter the length of Gray codes: "))
gray_codes = generate_gray_codes(n)

print(f"Gray codes of length {n}:")
for code in gray_codes:
    print(code)

How It Works

1. The function generate_gray_codes(n) takes an integer n as input and returns a list of Gray codes of length n.
2. If n is 1, there are only two possible Gray codes: ‘0’ and ‘1’. So, we return them as a list.
3. For n greater than 1, we recursively generate the Gray codes of length n-1 by calling generate_gray_codes(n - 1). Let’s assume this list is prev_gray_codes.
4. To generate Gray codes of length n, we follow these steps:
   • Iterate over each code in prev_gray_codes and prepend ‘0’ to it. Add the resulting code to gray_codes.
   • Iterate over each code in prev_gray_codes in reverse order and prepend ‘1’ to it. Add the resulting code to gray_codes.
5. Finally, return gray_codes, which will be the Gray codes of length n.

Input/Output: