Python Program to Generate Gray Codes using Recursion

Our website provided core java programs examples with output aid beginners and expert coders to test their knowledge gap and learn accordingly.

Recursive function:

In its definition, recursion is just calling the same function many times (this means, we are using that same function within its body).

Binary Code:

As previously stated, Binary Code is a Base-2 representation of a number. In Binary, all numbers are represented by simply two symbols: 0 and 1. Binary (also known as base-2) is a numerical system with only two digits: 0 and 1.

Gray Code:

A Gray Code is a method of encoding integers in which consecutive numbers differ by by one bit. Gray Code is created by arranging the binary numeral system in such a way that two consecutive values differ only by one bit.

The number of bits n has been specified. The task at hand is to generate n-bit Gray code. The Gray code is a binary number ordering in which two consecutive codewords differ by only one bit.

Examples:

Example1:

Input:

given number of bits = 5

Output:

Printing all 5 bits Gray Codes : 
['00000', '00001', '00011', '00010', '00110', '00111', '00101', '00100', '01100', '01101', '01111', '01110', '01010', 
'01011', '01001', '01000', '11000', '11001', '11011', '11010', '11110', '11111', '11101', '11100', '10100', '10101',
'10111', '10110', '10010', '10011', '10001', '10000']

Example2:

Input:

given number of bits = 7

Output:

Printing all 7 bits Gray Codes : 
['0000000', '0000001', '0000011', '0000010', '0000110', '0000111', '0000101', '0000100', '0001100', '0001101',
'0001111', '0001110', '0001010', '0001011', '0001001', '0001000', '0011000', '0011001', '0011011', '0011010',
'0011110', '0011111', '0011101', '0011100', '0010100', '0010101', '0010111', '0010110', '0010010', '0010011',
'0010001', '0010000', '0110000', '0110001', '0110011', '0110010', '0110110', '0110111', '0110101', '0110100',
'0111100', '0111101', '0111111', '0111110', '0111010', '0111011', '0111001', '0111000', '0101000', '0101001', 
'0101011', '0101010', '0101110', '0101111', '0101101', '0101100', '0100100', '0100101', '0100111', '0100110',
'0100010', '0100011', '0100001', '0100000', '1100000', '1100001', '1100011', '1100010', '1100110', '1100111',
'1100101', '1100100', '1101100', '1101101', '1101111', '1101110', '1101010', '1101011', '1101001', '1101000',
'1111000', '1111001', '1111011', '1111010', '1111110', '1111111', '1111101', '1111100', '1110100', '1110101',
'1110111', '1110110', '1110010', '1110011', '1110001', '1110000', '1010000', '1010001', '1010011', '1010010',
'1010110', '1010111', '1010101', '1010100', '1011100', '1011101', '1011111', '1011110', '1011010', '1011011',
'1011001', '1011000', '1001000', '1001001', '1001011', '1001010', '1001110', '1001111', '1001101', '1001100',
'1000100', '1000101', '1000111', '1000110', '1000010', '1000011', '1000001', '1000000']

Program to Generate Gray Codes using Recursion in Python

There are several ways to generate gray codes  using recursion some of them are:

• Using Recursion (Static Input)
• Using Recursion (User Input)

Method #1:Using Recursion (Static Input)

Approach:

• Give the value of numb as static input.
• There is a function called printGrayCodes that is defined.
• It accepts as an argument the number of bits n.
• It returns a list of n-bit Gray codes.
• To begin, the function obtains the (n – 1)-bit Gray code.
• The first half of the n-bit Gray codewords are simply the (n – 1)-bit Gray codewords prefixed with a 0.
• The second half of the n-bit Gray codewords is made up of (n – 1)-bit Gray codewords listed in reverse and prefixed with a 1.
• The 0-bit Gray code is essentially the empty string.

Below is the implementation:

def printGrayCodes(numb):
    # Return a list of n-bit Gray codes.
    if numb == 0:
        return ['']
    # The first half of the n-bit Gray codewords are simply the (n – 1)-bit Gray
    # codewords prefixed with a 0.
    firstHalfBits = printGrayCodes(numb - 1)
    secondHalfBits = firstHalfBits.copy()
    # The second half of the n-bit Gray codewords is made up of (n – 1)-bit Gray codewords
    # listed in reverse and prefixed with a 1.
    firstHalfBits = ['0' + code for code in firstHalfBits]
    secondHalfBits = ['1' + code for code in reversed(secondHalfBits)]
    # printing the result
    return firstHalfBits + secondHalfBits


# Give the value of number of bits as static input
numb = 5
# passing the given number of bits to print gray codes
getOutput = printGrayCodes(numb)
print('Printing all', numb, 'bits', 'Gray Codes : ')
print(getOutput)

Output:

Printing all 5 bits Gray Codes : 
['00000', '00001', '00011', '00010', '00110', '00111', '00101', '00100', '01100', '01101', '01111', '01110', '01010', 
'01011', '01001', '01000', '11000', '11001', '11011', '11010', '11110', '11111', '11101', '11100', '10100', '10101',
 '10111', '10110', '10010', '10011', '10001', '10000']

Method #2:Using Recursion (User Input)

Approach:

• Give some random number of bits as user input using int(input()) function.
• There is a function called printGrayCodes that is defined.
• It accepts as an argument the number of bits n.
• It returns a list of n-bit Gray codes.
• To begin, the function obtains the (n – 1)-bit Gray code.
• The first half of the n-bit Gray codewords are simply the (n – 1)-bit Gray codewords prefixed with a 0.
• The second half of the n-bit Gray codewords is made up of (n – 1)-bit Gray codewords listed in reverse and prefixed with a 1.
• The 0-bit Gray code is essentially the empty string.

Below is the implementation:

def printGrayCodes(numb):
    # Return a list of n-bit Gray codes.
    if numb == 0:
        return ['']
    # The first half of the n-bit Gray codewords are simply the (n – 1)-bit Gray
    # codewords prefixed with a 0.
    firstHalfBits = printGrayCodes(numb - 1)
    secondHalfBits = firstHalfBits.copy()
    # The second half of the n-bit Gray codewords is made up of (n – 1)-bit Gray codewords
    # listed in reverse and prefixed with a 1.
    firstHalfBits = ['0' + code for code in firstHalfBits]
    secondHalfBits = ['1' + code for code in reversed(secondHalfBits)]
    # printing the result
    return firstHalfBits + secondHalfBits


# Give the value of number of bits as static input
numb = int(input('Enter some random number of bits = '))
# passing the given number of bits to print gray codes
getOutput = printGrayCodes(numb)
print('Printing all', numb, 'bits', 'Gray Codes : ')
print(getOutput)

Output:

Enter some random number of bits = 7
Printing all 7 bits Gray Codes : 
['0000000', '0000001', '0000011', '0000010', '0000110', '0000111', '0000101', '0000100', '0001100', '0001101',
 '0001111', '0001110', '0001010', '0001011', '0001001', '0001000', '0011000', '0011001', '0011011', '0011010',
 '0011110', '0011111', '0011101', '0011100', '0010100', '0010101', '0010111', '0010110', '0010010', '0010011',
 '0010001', '0010000', '0110000', '0110001', '0110011', '0110010', '0110110', '0110111', '0110101', '0110100',
 '0111100', '0111101', '0111111', '0111110', '0111010', '0111011', '0111001', '0111000', '0101000', '0101001', 
'0101011', '0101010', '0101110', '0101111', '0101101', '0101100', '0100100', '0100101', '0100111', '0100110',
 '0100010', '0100011', '0100001', '0100000', '1100000', '1100001', '1100011', '1100010', '1100110', '1100111',
 '1100101', '1100100', '1101100', '1101101', '1101111', '1101110', '1101010', '1101011', '1101001', '1101000',
 '1111000', '1111001', '1111011', '1111010', '1111110', '1111111', '1111101', '1111100', '1110100', '1110101',
 '1110111', '1110110', '1110010', '1110011', '1110001', '1110000', '1010000', '1010001', '1010011', '1010010',
 '1010110', '1010111', '1010101', '1010100', '1011100', '1011101', '1011111', '1011110', '1011010', '1011011',
 '1011001', '1011000', '1001000', '1001001', '1001011', '1001010', '1001110', '1001111', '1001101', '1001100',
 '1000100', '1000101', '1000111', '1000110', '1000010', '1000011', '1000001', '1000000']

Related Programs:

• Python Program to Check Whether a String is a Palindrome or not Using Recursion
• Python Program to Find the Product of two Numbers Using Recursion
• Python Program to Find if a Number is Prime or Not Prime Using Recursion
• Python Program to Find the Fibonacci Series Using Recursion
• Python Program to Find the Power of a Number Using Recursion