Hello, I need help generating grey code via recursion. I am lost. For this probl

Question

Hello,

I need help generating grey code via recursion. I am lost. For this problem, I have to return an array list and take input of type integer. So, I have to write a Java method which produces, for a given k, all 2^k bit strings of length k, in a Grey Code ordering.

I'm not sure what my base case should be and how do I append a "0" and a "1" to produce the grey code. Thank the help.


public static ArrayList<String> greyCodes(int k){ //must have this method prototype
ArrayList<String> bits = new ArrayList<String>();

if(k<=0){ //in case k is zero, then it will return an empty string
bits.add("");
return bits;
}
if(k==1){
bits.add("0");
bits.add("1");
}
else{
//somehow I have to concatenate a "0", then reverse the list and add "1"
ArrayList<String> bitSmaller = new ArrayList<String>();



return bitSmaller=greyCodes(k-1);



}

Explanation / Answer

PS: Please rate my answer.

This program will print out the gray code on console. Instead of printing out, append them to your ArrayList. I think i'll leave that for you. Dont forget to rate the answer.

To compile: javac GrayCode.java 

To run: java GrayCode <number of bits>

public class GrayCode {

// append reverse of order n gray code to prefix string, and print
public static void yarg(String prefix, int n) {
if (n == 0) System.out.println(prefix);
else {
gray(prefix + "1", n - 1);
yarg(prefix + "0", n - 1);
}
}

// append order n gray code to end of prefix string, and print
public static void gray(String prefix, int n) {
if (n == 0) System.out.println(prefix);
else {
gray(prefix + "0", n - 1);
yarg(prefix + "1", n - 1);
}
}


public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
gray("", N);
}

}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.