shibly - 1 year ago 57
C Question

# 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 ..
}
``````

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[4-n] = 0;
int_buffer_rec(n - 1, length);
number[4-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);
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download