Generate All Strings of ‘n’ bits. Assume A[0….n-1] be an array of size n

Question

void binary(int n)
{
    if(n < 1)
        printf("%s\n",A);    // Assume A is a global variable
    else
    {
        A[n-1] = '0';
        binary(n-1);
        A[n-1] = '1';
        binary(n-1);
    }
}

Can anyone please explain the stack frames for n = 2? I mean when n = 2, I'm getting 00 when I'm doing a dry run. But there is also a 01 which I'm missing. Can someone please explain what stack frames are generated for this code?

Answer 1

Let us try to understand the code.

if(n < 1)
    printf("%s\n",arr);
else
{
    arr[n-1] = '0';
    binary(n-1);
    arr[n-1] = '1';
    binary(n-1);
}

We will follow a backwards approach since it is a recursive function.For instance lets say n = 1,

The method is called as binary(1);
arr[n-1] is set as ‘0’ (arr[1-1] = arr[0] = ‘0’)

Now we call binary(0);
since (n<1) we print arr (0 is printed)

The call returns to arr[n-1] = ‘1’
arr[1-1] is set as ‘1’ (arr[1-1] = arr[0] = ‘1’)

Now we call binary(0);
since (n<1) we print arr (1 is printed)

Thus, we got 2 outputs as possible bits 0 and 1.

Now let us suppose n = 2,

The method is called as binary(2) arr[2-1] is set as ‘0’ (arr[2-1] = arr[1] = ‘0’)

Now we call binary(1);
From the above explanation we know that binary(1) produces an output of 0 and 1 for arr[0]. Here arr[1] is set as 0. So we get the 2 outputs (00 and 01).

The function returns to arr[n-1] = ‘1’
arr[2-1] is set as 1 (arr[2-1] = arr[1] = ‘1’)

Again we call binary(1); This time arr[1] is set as ‘1’ and thus we get 2 more outputs (10 and 11).

We have a total of 4 outputs on screen..(00, 01, 10, 11) These are all the strings of 2 bits.

Similarly, you can work around for n = 3. arr[2] is set as ‘0’ and binary(2) is called. This produces (000, 010, 100, 110) arr[2] is then set as ‘1’ and binary(2) is called. This produces (001, 011, 101, 111). These are all the strings of 3 bits.

I hope this methodology makes it clear. Please feel free to ask anything else as well.

Answer 2

This is the recursion flow for n=3,