# 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`.