Learn Programming and technology with ease @ developerpublish.com

HomePythonPython Program to Generate Gray Codes using Recursion

# 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:

### You May Also Like

#### Python Program to Remove Duplicates from a Linked List

In this Python program, we will create a singly linked list and remove duplicate elements from it. A linked list...

#### Python Program to Solve the Celebrity Problem

This Python program solves the Celebrity Problem by finding a person who is known by everyone but does not know...

#### Python Program to Solve n-Queen Problem with Recursion

This Python program uses a recursive approach to solve the n-Queens problem. It explores all possible combinations of queen placements...