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

Geoponics

What have you achieved so far? – Canaigre

so with the code above, you call rec(0, 4) and rec(1, 4), what exactly do you expect? – Baber

@Howard, I have added more code. Please notice. – Geoponics

@ExP, for rec(0,4) expecting to print first 8 row starting with zero and with rec(1,4) expecting to print last 8 row starting with one. – Geoponics

Answer 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);

Purlieu

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

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. – Purlieu

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

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. – Purlieu

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. – Geoponics

@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. – Purlieu

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. – Geoponics

@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 ? – Purlieu

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

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. – Purlieu

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

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

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

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. – Purlieu

let us continue this discussion in chat – Purlieu

Answer 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

Dilative

//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 ? – Geoponics

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

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

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

Answer 3

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);
}

Feltonfelts

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 – Feltonfelts

Answer 4

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

Samuel

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

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

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

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. – Scutiform

Answer 5

Let us start by designing the prototype of the recursive function. Hopefully, it'll make sense from there. Take a look at a non-recursive version of this code, and you'll need the same variables. You don't need to pass any of them as arguments, but I'd prefer to pass them all, and make the solution as flexible and modular as possible. Consider the return value, too. That should probably indicate some sort of success, in order to mimic consistency with the C standard library.

int count_r(char *destination, /* The storage for the function to store *
                                *     the 0s and 1s as we count.        */
            size_t length,     /* The number of digits in the number.   */
            char *digit);      /* The set of digits                     */

---

Now let us focus on designing the first iteration. Like in primary school, we start by defining our count_r to iterate only single digits at a time. Once we can prove that it knows how to count from 0 to 9, we introduce it to double digits... but for now, one step at a time.

Let us assume destination is initialised to contain length bytes of digits[0], prior to the first call. This initialisation is done by the caller, and the caller would presumably output that pre-initialised array before calling. The first iteration should modify only one byte: The one indicated by length, and then return to the caller.

int count_r(char *destination, size_t length, char *digit) {
    /* The position of the right-most digit is before the '\0' in destination, *
     *     so we need to decrement length                                      */
    length--;

    /* Find the digit at the very end of destination, within our "digit" parameter */
    char *d = strchr(digit, destination[length]);

    /* d[1] points to the next digit (or '\0') */
    destination[length] = d[1];
    return 0;
}

The caller then presumably prints the array, and calls count_r again with the same buffer to increment the counter. This works with different bases, and by reversing the digit string we can decrement instead of incrementing. However, as we'll soon see, it fails after it reaches the highest number it can count to: 'F' in the example below.

int main(void) {
    char num[] = "0";
    do {
        puts(num);
    } while (count_r(num, strlen(num), "0123456789ABCDEF") == 0);
}

---

When the time comes for counting higher, d[1] will be '\0' as it will have iterated beyond the set of digits and into the null terminator for the string. Let us consider adding code to handle our second iteration.

A bit of code is needed to set destination[length] back to the first digit and recursively move left onto the next digit. This occurs when d[1] == '\0', so we can write an if (...) { ... } branch to handle that.

There is a problem when length is passed in as 0, which we would discover after implementing the change mentioned just now. Here is where the function should return 1 to indicating that counting has finished, because it has moved as far left as possible and reached the highest number possible.

void count_r(char *destination, size_t length, char *digit) {
    /* The position of the right-most digit is before the '\0' in destination, *
     *     so we need to decrement length                                      */
    if (length-- == 0) { return 1; }

    /* Find the digit at the very end of destination, within our "digit" parameter */
    char *d = strchr(digit, destination[length]);

    /* d[1] points to the next digit (or '\0') */
    if (d[1] == '\0') {
        /* Set destination[length] to the first digit */
        destination[length] = digit[0];
        /* Recurse onto the next digit. We've already decremented length */
        return count_r(destination, length, digit);
    }

    destination[length] = d[1];
    return 0;
}

After adding a few assertions (eg. assert(strlen(digit) > 1);) and writing some testcases, we might then decide that this function is ready for production. I hope I was able to help. :)

Macdonald

Answer 6

Recursion is a programming technique that allows the programmer to express operations in terms of themselves. In C and C++ , this takes the form of a function that calls itself.

#include<iostream>
#include<cstdio>
using namespace std;
void rec(int val)
{
  if(val<16)
  {
    printf("%u%u%u%u", val>>3, (val&4)>>2, (val&2)>>1, val&1);
    printf("\n");
    rec(++val);    //calling val+1 here
  }
  return;
}
int main()
{
   rec(0);  //calling recursion for 0
}

This gives you exact output you want..!

If you don't want to use bit shift operators ..

#include<iostream>
#include<cstdio>
using namespace std;
void rec(int val)
{
   if(val<16)
   {
     for(int b=val,a=8,i=0;i<4;b%=a,a/=2,i++)
     printf("%u",(b/a));
     printf("\n");
     rec(++val);// calling val+1 here
   }
   return;
}

int main()
{
   rec(0);//calling recursion for 0
}

Wolfort

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

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

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

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

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

@Wolfort 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? – Cacomistle

@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 https://mcmap.net/q/73746/-39-printf-39-vs-39-cout-39-in-c – Wolfort

@Wolfort 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 – Cacomistle

here is the reference you can see where printf is declared – Cacomistle

@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 . – Wolfort

@Wolfort 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. – Cacomistle

Answer 7

This problem can be generalized to obtain binary combination of any length by using recursion. For example, if you want to get all binary combinations of length=4, just call printBinaryCombination("????", 0) (i.e. four ?s need to replaced with 0 or 1).

The corresponding code is as follows:

void printBinaryCombination(string str, int current)
{
    int length = str.length();
    if (length == 0)
        return;

    if (current == length)
        printf("%s\n", str.c_str());
    else
    {
        if (str[current] == '?')
        {
            str[current] = '0';
            printBinaryCombination(str, current+1);

            str[current] = '1';
            printBinaryCombination(str, current+1);

            // change back for next time
            str[current] = '?';
        }
        else
            printBinaryCombination(str, current+1);
    }
}

EDIT: Actually, the above function is also powerful to handle all binary combinations that contains random number of ?s, each of which can be 0 or 1. For example, if you call printBinaryCombination("1??0", 0), it will print:

1000
1010
1100
1110

Usia

Answer 8

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..

Dallasdalli

Answer 9

SOLN 1: a more generalized answer(compilable under c90, c99). booleans being output as int. Limitations :
1) uses math library.(its heavier so).

#include<stdio.h>
#include<math.h>
#define MAXBITS 4
//#define MAXVALUES (((int)pow(2,maxb))-1)
const int MAXVALUES = (((int)pow(2,maxb))-1) //if this gives warning then use #define version.

void bin(int val,int total)
{
    int i = 0;          
    if(val <= MAXVALUES)            //can write pow(2,total-1)-1 but anyways..
    {
        for(i =0 ; i < total;i++)
        {
            printf("%d",!!(val&(int)pow(2,total-i-1)));
        }           
        printf("\n");

    }
    else return;
    bin(val+1,total);
}

int main()
{
    setbuf(stdout,NULL);
    bin(0,MAXBITS);//4 bits 
    return 0;
}

Soln 2 :This can be done by char printing. no shift operator.

limitation(s) :
1) it can print(correctly) only upto 15(dec) or 0x0F(hex) values.
2) a total of
(5 * sizeof(char) * total) + (( total + 2) * (sizeof(int) + sizeof(int))) created on stack(so wasteful).

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define MAXVALUES 15
#define MAXBITS 4
void bin(int val,int total) //@prototype void bin(int val);remove redundant total.
{
    char *s = malloc(sizeof(char)*(total+1)); //cant declare variable array(atleast pre c99)
    int i = 0;
    if(val <= MAXVALUES )
    {
        for(i =0 ; i < total;i++)
        {
        s[total - i-1] = !!(val&(int)pow(2,i)) + '0';
        }
        s[total] = '\0';
        printf("%s\n",s);
    }
    else return;
    bin(val+1,total);
}

int main()
{
    bin(0,MAXBITS);//4 bits 
    return 0;
}

Abbreviate

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

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

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

@Wolfort 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 – Cacomistle

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

Avoid using pow! You can use << instead. – Scutiform

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

Answer 10

This general purpose c++ code works for any number of bits. just change const int num to any number of bits you want to generate binary code of...

const int num=3;
string code="";

void GenerateBinaryCode(string str,unsigned int n){
    if(n==0){
        cout<<str<<endl;
    }
    else{
        str[num-n]='0';
        GenerateBinaryCode(str,  n-1);
        str[num-n]='1';
        GenerateBinaryCode(str, n-1);
    }
}
int main(){
    for(int i=0; i<num; i++)
        code+="x";

    GenerateBinaryCode(code,num);

}

Seed

Answer 11

Here's a recursive implementation in C using only an int 2D array (no strings, chars or bitshifting) for arbitrary bit lengths.

static void btable(int* a, int i, int n, int k, size_t len) {
    if (k >= len)
        return;
    for (int j = (i+n)/2; j < n; j++)
        *(a+j*len+k) = 1;
    btable(a,i,(i+n)/2,k+1,len);
    btable(a,(i+n)/2,n,k+1,len);
}

Then you can call the function with

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int main(void) {

    int n = 4;
    int (*a)[n] = malloc(sizeof(int[(int)pow(2,n)][n]));
    btable(*a,0,pow(2,n),0,n);

    for (int i = 0; i < pow(2,n); i++) { // verify output
        for (int j = 0; j < n; j++)
            printf("%d",a[i][j]);
        printf("\n");
    }

    return 0;
}

Laws

Answer 12

Before to present the final solution, I'll show two functions that we can use for our goal.

The main idea of the next function is to add the elements of the l1 list to each list that is contained in l2. For example:

l1 = [0]
l2 = [ [1,1] , [1,0] ]
then 
f1(l1,l2) = [ [0,1,1] ,[0,1,0]]


    def f1(l1:List[Int],l2:List[List[Int]]): List[List[Int]] = l2.map{ r=> l1:::r}

The first parameter is a list that contains a list of integers that will be added to each list of numbers contained in the l2 list. For example:

l1 = [ [0] , [1]]
l2 = [ [1,0], [1,1] ]
f(l1,l2) = [ [0,1,0],[0,1,1], [1,1,0],[1,1,1] ]


    def f(l1:List[List[Int]],l2:List[List[Int]]): List[List[Int]] = l1.map{ r=> f1(r,l2)} flatten

Now, that we have the auxiliary methods, we create the function that will solve the requirement

/**
n : The max number of digits that the binary number can contain
*/

    def binaryNumbers(n:Int):List[List[Int]] = n match {
     case 1 => List(List(0),List(1))
     case _ => f( List(List(0),List(1)) , binaryNumbers(n-1) )
    }

Example: binaryNumbers(2) = List( List(0,0), List(0,1), List(1,0), List(1,1) )

Blueweed

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