1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Recursion code for generating Gray Code in C

  1. Dec 3, 2009 #1
    1. The problem statement, all variables and given/known data

    I need to implement a recursive code for generating the Gray code for a given number of bits. For example, if the input bit is 1 it generates Gray code for 1 bit number i.e 0 and 1. Given 2, it generates Gray code for 2 bit numbers i.e 00 and 01 and so on. I don't understand how to implement and what should be the base case.

    I'd be really grateful in case of any help.


    2. Relevant equations

    3. The attempt at a solution
  2. jcsd
  3. Dec 4, 2009 #2
    First, a few pointers about recursion:
    - Find the base case
    - Implement that first
    - Define when you should go in recursion
    - If the recursive call succeeds once, it will always succeed

    As you may know, recursion is, essentially, solving a huge problem by solving the smaller parts of the problem which are, in essence, the same problem as the huge one. The postulate is that when all smaller problems have been solved, the problem as a whole has been solved.

    Anyway, enough of that.

    Your base case is 1 bit, which results in G = {0,1}. To go to n = 2, reflect the bits (it becomes {1,0}), concatenate that list with the original list and append the 0 to the original list and the 1 to the reflected list, resulting in G = {{00},{01},{11},{10}}.

    n = 1

    Reflect and concatenate:

    Append zeros and ones:

    We now have n = 2.

    In short, you pass a number of bits to your method, n that specifies the Grey code for n bits. Recursively go down to one, where you can create the base for n = 1, then work your way back up.

    Code (Text):

    char[] bits

    void grayCode(int numBits) {
      if(bits == 1) {
        bits = ['0','1'];
      } else {
        if(numBits != 1) {
          grayCode(numBits - 1);
        char[] mirroredBits = reverse(bits);
        //for the first n bits, append 0
        //for the last n bits, append 1
    Okay, it's ugly and not C, but I'm sure you can translate it to proper C which will output exactly what you need. This code goes down to your base case, constructs it and then expands upon the base case until the specified number of bits has been reached.
    Last edited: Dec 4, 2009
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook