CODEWITHSUNDEEP
javaalgorithm
batman
batman

Reputation: 3685

How this code does exactly it needs to do?

Here is the code for printing all possibilities of binary number for n equals 3:

public class Main {

    static void binary(int N, int[] A) {
        if(N < 1)
            System.out.println(Arrays.toString(A));
        else
        {
            A[N-1] = 0;
            binary(N-1,A);
            A[N-1] = 1;
            binary(N-1,A);
        }
    }

    public static void main(String[] args) {
        int[] a = new int[3];
        binary(3,a);
    }
}

The code works perfectly fine. I could able to see there are two recursion calls, I couldn't able to understand how this works. Why there is a need for two recursion calls?

Upvotes: 2

Views: 84

Answers (2)

vladich
vladich

Reputation: 608

Every additional bit multiplies the number of possible values 2 times. it means you have

            0        and         1        - first bit
then    00     10    and     01     11    - second bit
then 000 100 010 110 and  001 101 011 111 - third bit and so on

So for every call you should make two more to process both possible values (0 and 1) of the next bit

Upvotes: 3

PartlyCloudy
PartlyCloudy

Reputation: 701

To get all possible binary representations of some length, you can consider it as an array of bits with value 0 or 1.

The recursion can be explained with the following wishful thinking - assuming we can generate all binary representations of length N-1, how do we generate all binary representations of length N? The answer - append 0 at the start of all N-1 representations, and add that list to the one created by appending 1 at the start of all N-1 representations. This wishful thinking is obtained by making the two method calls.

Lets follow how this program operates for N=2: We will note the values of the array as [?,?]:

  1. N = 2, A = [?, 0], call binary(1,A)
  2. N = 1, A = [0, 0], call binary(0,A)
  3. N = 0, print [0,0]
  4. N = 1, A = [1, 0] call binary (0,A)
  5. N = 0, print [1,0]
  6. N = 2, A = [?, 1], call binary (1,A)
  7. N = 1, A = [0, 1], call binary(0,A)
  8. N = 0, print [0,1]
  9. N = 1, A = [1, 1] call binary (0,A)
  10. N = 0, print [1,1]

Upvotes: 1

Related Questions