Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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 ..
}
like image 410
shibly Avatar asked Apr 22 '13 15:04

shibly


People also ask

How many binary combinations are there with 4 bits?

There is obviously a problem with this since 4 bits gives 16 possible combinations, and there are only 10 unique decimal digits, 0 to 9.

How do you find binary equivalent of a number using recursion in C?

The function convert() is used to convert a number decimal system to binary system using recursion.


1 Answers

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);
like image 98
15 revs, 3 users 99% Avatar answered Oct 01 '22 00:10

15 revs, 3 users 99%