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**

- The function
`generate_gray_codes(n)`

takes an integer`n`

as input and returns a list of Gray codes of length`n`

. - If
`n`

is 1, there are only two possible Gray codes: ‘0’ and ‘1’. So, we return them as a list. - 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`

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

.

- Iterate over each code in
- Finally, return
`gray_codes`

, which will be the Gray codes of length`n`

.

## Leave a Review