How can i generate 4 bit binary combination using recursion in C for 0,1?

Question

For this array, trying something like this:

void rollover(int val,int count) {  
    if(count==0) {
        return;
    }
    printf("%d ",val);
    count--;
    rollover(val,count);    
}
int main() {
    int arr[]={0,1};
    for(int i=0;i<=1;i++) {
        rollover(arr[i],4);
    }
    printf("\n");
    return 0;
}

Expected output using recursion method:

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

Can't understand how to write that rec function. I have spent several hours to solve it. Can someone assist to write that function?

I am/was trying to do something like G_G posted below. How can i write such recursion function? Do i have to use one for loop to call that recursion function or two for loop with recursion or should i call the recursion function twice? For example:

void rollover(int val,int count) {  
    if(count==0) {
        return;
    }
    printf("%d ",val);
    count--;
    rollover(val,count);
    //.. do something if necessary ..
    rollover(val,count);
    //.. do something if necessary ..
}

Solution 1

Simplest solution : binary conversion, no recursion

for(int i = 0; i < 16: ++i) {
    printf("%u%u%u%u", i/8%2, i/4%2, i/2%2, i%2);  
}

See MOHAMED's answer for a recursive version of this loop

---

Binary recursion used by the following solutions

          _ 000
   _ 00 _/
  /      \_ 001
 0        _ 010
  \_ 01 _/
         \_ 011
          _ 100
   _ 10 _/
  /      \_ 101
 1        _ 110
  \_ 11 _/
         \_ 111

Recursive solution using char* buffer, no binary conversion

void char_buffer_rec(char number[4], int n) {
    if(n > 0) {
        number[4-n] = '0';
        char_buffer_rec(number, n - 1);
        number[4-n] = '1';
        char_buffer_rec(number, n - 1);
    }
    else {
        printf("%s\n", number);
    }
}

usage :

char number[5] = {0};
char_buffer_rec(number, 4);

Recursive solution using only int, no buffer, no binary conversion

void int_ten_rec(int number, int tenpower) {
    if(tenpower > 0) {
        int_ten_rec(number, tenpower/10);
        int_ten_rec(number + tenpower, tenpower/10);
    }
    else {
        printf("%04u\n", number);
    }
}

usage :

int_ten_rec(0, 1000);

Another version of this solution replacing tenpower width bitwidth, replacing the printf width with a variable padding depending on the length variable. length could be defined as a new parameter, a program constant, etc.

void int_rec(int number, int bitwidth) {
    static int length = bitwidth;
    int i, n;
    if(bitwidth > 0) {
        int_rec(number, bitwidth-1);
        /* n := 10^(bitwidth-2) */
        for(i=0,n=1;i<bitwidth-1;++i,n*=10);
        int_rec(number + n, bitwidth-1);
    }
    else {
        /* i := number of digit in 'number' */
        for(i=1,n=number;n>=10;++i,n/=10);
        /* print (length-i) zeros */
        for(n=i; n<length; ++n) printf("0");
        printf("%u\n", number);
    }
}

usage :

int_rec(0, 4);

Tree Solution, recursive using char* buffer, no binary conversion

struct Node {
    int val;
    struct Node *left, *right;
};

void build_tree(struct Node* tree, int n) {
    if(n > 0) {
        tree->left = (Node*)malloc(sizeof(Node));
        tree->right= (Node*)malloc(sizeof(Node));
        tree->left->val = 0;
        build_tree(tree->left, n - 1);
        tree->right->val = 1;
        build_tree(tree->right, n - 1);
    }
    else {
        tree->left = tree->right = NULL;
    }
}

void print_tree(struct Node* tree, char* buffer, int index) {
    if(tree->left != NULL && tree->right != NULL) {
        sprintf(buffer+index, "%u", tree->val);
        print_tree(tree->left, buffer, index+1);
        sprintf(buffer+index, "%u", tree->val);
        print_tree(tree->right, buffer, index+1);
    }
    else {
        printf("%s%u\n", buffer, tree->val);
    }
}

usage :

    char buffer[5] = {0};
    Node* tree = (Node*)malloc(sizeof(Node));
    tree->val = 0;
    build_tree(tree, 4);
    print_tree(tree, buffer, 0);

But this would print an additional 0 at the begining of each line, to avoid this, build two smaller trees :

    Node* tree0 = (Node*)malloc(sizeof(Node));
    Node* tree1 = (Node*)malloc(sizeof(Node));
    tree0->val = 0;
    tree1->val = 1;
    build_tree(tree0, 3);
    build_tree(tree1, 3);
    print_tree(tree0, buffer, 0);
    print_tree(tree1, buffer, 0);

Recursive solution using int* array

#define MAX_LENGTH 32
int number[MAX_LENGTH];
void int_buffer_rec(int n, int length) {
    if(n > 0) {
        number[length - n] = 0;
        int_buffer_rec(n - 1, length);
        number[length - n] = 1;
        int_buffer_rec(n - 1, length);
    }
    else {
        for(int i = 0; i < length; ++i) {
            printf("%u", number[i]);
        }
        printf("\n");
    }
}

usage :

int_buffer_rec(4, 4);

Solution 2

the recursion could be done with +1

void f(unsigned int x)
{
   printf("%u%u%u%u\n",
          (x>>3)&0x1,
          (x>>2)&0x1,
          (x>>1)&0x1,
          x&0x1);
   if(x==0xF) return;
   else f(x+1);
}

int main(void)
{
    f(0);
}

Execution:

$ ./test
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

Solution 3

I tried to limit my solution using to the same arguments but I would definitively add an extra argument to know the initial value of count.

void rec(int val, int count) {
    if (count <= 1) {
        int i;
        int f = 0;
        for (i = sizeof(int) * 8; i >= 0; i--) {
            f |= (val >> i) & 1;
            if (f) {
                printf("%d", (val >> i) & 1);
            }
        }
        printf("\n");
    } else {
        rec(val * 2, count - 1);
        rec(val * 2 + 1, count - 1);
    }
}

Output:

1
10
11
100
101
110
111
1000
1001
1010
1011
1100
1101
1110
1111

In order to add the leading 0, I added an argument :

#include <stdio.h>

void rec2(int val, int count, int b) {
    if (count <= 1) {
        int i;
        for (i = b - 1; i >= 0; i--) {
            printf("%d", (val >> i) & 1);
        }
        printf("\n");
    } else {
        rec2(val * 2, count - 1, b);
        rec2(val * 2 + 1, count - 1, b);
    }
}

void rec(int val, int count) {
    rec2(val, count, count);
}

int main() {
    rec(0, 4);
    rec(1, 4);
    return 0;
}

Output:

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

Solution 4

just traverse DFS a binary tree of depth 4, going left is 0, going right is 1.

tr(int dep, int val)
{
   if(dep == 4)
   {
     printf("\n");
   }
   else
   {
     printf("%d", val);
     tr(dep+1, 0); // going left
     tr(dep+1, 1); // going right
   }

   return;
}

int main()
{
   tr(0,0);
}

Solution 5

To generate n bit combination you asked for(you asked for n=4) general recursive implementation for any n would be:

Main function:

vector<string> ve,ve1;
int main(int argc, char const *argv[])
{
    /* code */
    int n;
    cin>>n;
    generate("0",n,true);
    generate("1",n,false);
    for(int i=0;i<ve.size();i++){
        cout<<ve[i]<<endl;
    }
    for(int i=0;i<ve1.size();i++){
        cout<<ve1[i]<<endl;
    }
    return 0;
}

Generate function which recursively generates the binary strings:

void generate(string s,int n,bool b){
    if(n==1){
        if(b==true){
            ve.push_back(s);
        }
        else{
            ve1.push_back(s);
        }
        return;
    }else{
        generate(s+"0",n-1,b);
        generate(s+"1",n-1,b);
    }
}

Hope this helps..

View more solutions

Comments

[shibly]

//print here the first 4 bits of x = right side 4 bits = less significant bits ? That means, i have to convert from decimal to binary ?

[zakinster]

But that's more a stack-loop than a real recursion.

[MOHAMED]

@guru I updated my answer concerning the print of 4 first bits of x

[shibly]

Actually i don't want to convert from decimal to binary or to use shift operator.

[shibly]

Thank You. But can you rewrite that code without making string or without using characters. Can you use integer for recursion instead of characters?

[zakinster]

You could use an integer (or more logical, boolean) array as a buffer, but you would have to print it manually at the end which is less convenient than a char array. In any case you can't do this without some sort of accumulation buffer, if you want to use only int as recursion parameters (as in MOHAMED's answer), you would have to convert it to binary before printing it and a simple loop would do the same job.

[shibly]

Can you rewrite that code to make a binary tree(depth=4), left side 0 and right side 1 ?

[zakinster]

Well that's basically what this algorithm is doing, except it doesn't actually store the tree in memory. Building a tree won't be more helpful because while traversing the tree in depth you won't be able to print before reaching the leafs so you'll still need a buffer to store the path you've taken in the tree. See my last edit for an example using a binary tree, you'll see my initial solution is a simplified version of the last one.

[Gianluca Ghettini]

I edited the answer, however the code will not print the whole bit pattern everytime but just the portions that changes from the previous one

[shibly]

Thank you for your reply. But i am looking for a answer like G_G posted. Tree looks complex here for this. Using recursion only can do this.

[zakinster]

@guru I agree that building a tree is not very helpful, it was just in answer to your comment. G_G's answer won't be able to print your output without using a buffer, if you add a buffer to G_G's answer, you got basically my initial answer. But see my last edit for another solution that does not involve character buffer but only integers.

[Maxime Chéramy]

Why bin(0,20) ? I thought that the total value meant the number of bits, not the maximum value. See example.

[Koushik Shetty]

total is just redundant i can reduce the code further. well i'l localize the answer it to the current code.

[shibly]

Thank You for your answer. But i am looking for a solution without using shifting/bitwise operator. Only using recursion and printf() .

[Koushik Shetty]

@guru the first solution is very generic. you could use that

[shibly]

Also converting from decimal to binary is not allowed. Can it be re-writen without doing conversion from decimal to binary?

[shibly]

Can you follow the exact pattern of the 4 bit output? Like 0000,0001 ?

[shibly]

Thank You for your answers. Building tree is not expected here. But can you please keep/post your solution/code of tree here, it may help/need for other case. Just keep it as a store.

[MissingNumber]

@guru Can you please update your question completely with the information What exactly do you expect from your function ?

[Koushik Shetty]

@MissingNumber Yes whats wrong in MAXBITS being 4, if you need a 4 bit binary value?infact if i give n bits it will print upto 2^n

[Koushik Shetty]

@MissingNumber oh you must be referring to #define MAXVALUE 5 and op had asked for 4? i changed it. typo.

[Koushik Shetty]

@MissingNumber you cannot use printf() without <cstdio>. i'l edit

[MissingNumber]

@Koushik I think you have missed to look at <iostream> ..!! And I have not specified this as C code !

[Koushik Shetty]

@MissingNumber yeah then you cant use printf() in c++ without a equivalent header. you have not specified it as c but you are using c functions. moreover you should be using cout?

[MissingNumber]

@Koushik No you have mistaken .. We can use printf() in c++ with only <iostream> you please test it and comment..!! And if you need further reference ,here is one good answer stackoverflow.com/questions/2872543/printf-vs-cout-in-c

[Koushik Shetty]

@MissingNumber you did not read the answer properly there in the link. they are comparing printf and cout. 2) printf is not decalred in iostream at all. its a cfunction declared in namespace std in cstdio. please refer documentation. if you still have doubts dont include <cstdio> and compile in g++ or your c++ compiler

[Koushik Shetty]

here is the reference you can see where printf is declared

[MissingNumber]

@Koushik yeah it is in namespace std; Agreed but that is what i have written in my code which just meant that Both of us are correct . As i need not add cstdio as i said , and it is mandate as you , which indirectly included as std .

[Koushik Shetty]

@MissingNumber no just because it is in namespace std doesnt mean you cannot include cstdio namespaces are open that means you can add to a namespace in a different header file, and you have to include that header to know the presence of a member. even if you write using namespace std; and include only iostream, then whats in iostream within namespace std only is visible.

[zakinster]

@guru I put the tree solution back and I reorganize the post. Did you check my recursive solutions using only int, no buffer, no binary conversion, it really looks like what you're looking for ?

[Maxime Chéramy]

Avoid using pow! You can use << instead.

[Koushik Shetty]

@Maxime sure i can use(infact thats what i used first) but OP says no bitwise operators!

[Maxime Chéramy]

Yes, see my edit. Also works with any number of bits, that's the big difference with the other solutions.

[shibly]

Is it possible to avoid using bitwise/shifting operator somehow? Is it possible to avoid converting from decimal to binary?

[shibly]

"Recursive solution using only int, no buffer, no binary conversion" , yes that looks good. Can you post the complete code with the main function?

[zakinster]

For each of my examples, you just have to put the usage part in an empty main to make it work. int main() { rec(0, 4); } should work for the second version.

[shibly]

if(p > 0) { , what is p here?

[zakinster]

Sorry forgot to rename it, it's actually tenpower.

[shibly]

rec(0, 1000); , you have to call it with 1000, why? How does 1000 come? But rec(0,4) doesn't work.

[zakinster]

tenpower must be a power of ten. For n bits numbers, the recursion starts with tenpower = 10^(n-1), tenpower is divided by 10 at each recursion and it stops when tenpower = 0. It is used to simplify the iteration with regard to the second version which uses bitwidth instead and is directly called with the number of bits.

[zakinster]

let us continue this discussion in chat

[Maxime Chéramy]

Most probably but I don't see the point. It's not a complicated operator and the other alternatives will be slower for most of them if not all.

[moggi]

The question author explicitly asked how to solve the problem in C.