Count Binary recursion?

Question

Write a method countBinary that accepts an integer n as a parameter and that prints all binary numbers that have n digits in ascending order, printing each value on a separate line. All n digits should be shown for all numbers, including leading zeros if necessary. You may assume that n is non-negative. If n is 0, a blank line of output should be produced. Do not use a loop in your solution; implement it recursively.

The issue Im having with this is I don't know how I would print the zeros and ones, since n is the only parameter I can have. I also cannot use a for loop and put my recursive call in the loop, so Im sorta stuck. this is what I have so far:

    public static void countBinary(int n){
if (n < 0) {
    throw new IllegalArgumentException();
}if(n == 0){
    System.out.print("");
}else{
    countBinary(n - 1);
    System.out.println(n ); // I tried doing n + "0" and + "1" did not work
    countBinary(n - 1 );
    System.out.print(n );
   // store += n;

}

}

And here is my output for countBinary(2):

When it should be this:

I am getting the right amount of "levels" for every other line which is strange, but Im really stuck

Note: this is NOT homework, simply practice. THanks!

Ted Hopp · Accepted Answer · 2015-12-06 19:39:01Z

You're on the right track with recursing twice. The concept is to print a "0" followed by an (n-1)-digit number, then a "1" followed by an (n-1)-digit number. The trick is to figure out how to handle the fact that for n > 1, there are many (n-1)-digit numbers and they each need to have that "0" or "1" in front of them. The way to handle that is to not actually print the "0" or "1" but to pass it down the recursion until you are ready to print each entire line. For that, you'll need an auxiliary method to do the actual recursion and you can use a char[], a StringBuilder, or even a String for the pending output so far. (I'd use the first and the second is fine too. I'd avoid using a String because it will generate a new String each time you need to add a "0" or "1"—a lot of garbage.)

Here's my solution:

public static void countBinary(int n){
    if (n < 0) {
        throw new IllegalArgumentException();
    }
    countBinary(new char[n], n);
}

private static void countBinary(char[] prefix, int n) {
    if (n == 0) {
        // base case -- no more recursion
        System.out.println(prefix);
    } else {
        // position next digit counting from the right so output is in increasing order
        final int i = prefix.length - n;

        // prefix a '0' and recurse
        prefix[i] = '0';
        countBinary(prefix, n-1);

        // prefix a '1' and recurse
        prefix[i] = '1';
        countBinary(prefix, n-1);
    }
}

Aracurunir · Accepted Answer · 2015-12-06 19:36:35Z

0

I don't believe the "NOT homework" thing, but anyways.
You want to print binary numbers by recursion. We can not do this by only having n as a single parameter. Because if we want to print a number of n digits haven the first x digits and then letting recursion add the oder y we need to know what the first x digits where.
That means, if someone tells me: "Print all binary numbers with n digits", I say: fine, this can be done by recursively printing all numbers with n digits and adding "" before them.

Now when someone asks me to print all numbers with n digits and adding "s" before it, I ask tell somebody else "Please print all binary numbers with n-1 digits and a "s" and 0 in front of it" because my number could start with 0.
After that I tell someone else "Please print all binary numbers with n-1 digits and a "s" and 1 in front of it" as my nubmer could also start with a 1.

This translates to code as follows:

// print all numbers with n digits
public static void printBinaryNumber(int n){
    // print all numbers with n digits recursively adding ""
    printBinaryNumbersRec("", n);
}

public static void printBinaryNumbersRec(String s, int n){
    if(n < 0) throw new IllegalArgumentException();
    if(n == 0) {
        // if I should print all numbers with 0 digits and add s before them
        // I just print s and am done
        System.out.println(s);
        return;
    }
    // add an additional 0 to s and print all numbers with n-1 digits
    printBinaryNumbersRec(s + "0", n-1);
    // add an additional 1 to s and print all numbers with n-1 digits
    printBinaryNumbersRec(s + "1", n-1);
}

answered Dec 6, 2015 at 19:36

Aracurunir

6356 silver badges10 bronze badges

3 Comments

thatsnifty Over a year ago

This is definitely not homework haha I swear. Im using Practice it and am trying to get this recursion thing down. Anyway, practice it doesn't allow me to use more than one parameter. My original solution for this was the same as what you posted.

Aracurunir Over a year ago

I don't think that your recursive function is meant to be limited to only one parameter, because it makes no sense that way. You could change it to only use one parameter by making s a public static variable. But this would make for a very very ugly solution and I don't suppose this is the goal of the excercise.

thatsnifty Over a year ago

I definitely understand that! It doesn't really make sense! But thanks for the response!

Collectives™ on Stack Overflow

Count Binary recursion?

2 Answers 2

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related