Printing n-bit binary strings in lexicographical order

[Dhanika]

Greetings everyone! I hope to learn and become better in programming. But honestly, my heart fails me everytime I face a new assignment. This one is just another heartache.

Thing is, the question wants me to print out n-bit strings in lexicographical order ( meaning increasing order ). And I must use recursion. I am new to this concept let alone c++. I hope you can guide me here.

So the output of this program of mine is like so:
n = 1;
00
01

n=2;
00
01
00
01
00

000
001
000
001...

But, It needs to be like this :
n=1
0
1

n=2
00
01
10
11...

Can anyone tell me what i did wrong? and please tell me how to correct this. I know its simple, and I do apologize if this question has been asked before, but please teach me.

Thanks.
Dhanika.

My code:

#include<iostream>
#include<string>
using namespace std;

void printAllBitStrings(int n, string binary){
       if (n == 1) {
        cout << "0" << endl;
        cout << "1" << endl;}
      else {
        printAllBitStrings(n - 1, binary  );
        binary[n] = '0';
        printAllBitStrings(n - 1, binary  );
        binary[n] = '1';
     }
} 
    
int main(){
    
    string binary;
    int n;
    cin >> n;
   
    for(int i = 0; i < n; i++){
            binary += "0";
            printAllBitStrings( n, binary);
            cout << endl;
            } 
    return 0;  
}

[tetron]

I suspect that this kind of question is just homework so perhaps I should not be answering it.

Binary = base 2
there is a function that will tell you the remainder of any number
called modulo and use the % sign

so 5%3 = 2;
as an integer representation of a binary to get the last digit
int binary_digit = i%2
to get the next digit you can divide
i = i/2; or i /= 2;
before doing this iteratively
you should check that i > 2
if not you want to
stop.

Greetings everyone! I hope to learn and become better in programming. But honestly, my heart fails me everytime I face a new assignment. This one is just another heartache.

Thing is, the question wants me to print out n-bit strings in lexicographical order ( meaning increasing order ). And I must use recursion. I am new to this concept let alone c++. I hope you can guide me here.

Recursion means calling the function from within itself and though this isn't appropriate for the current task it is a teaching assignment.

so you call the function from within in the function as you are doing
but be careful if you get it wrong it will never stop!

void GetBinaryString(int &i, std::string &binary_as_a _string)
{
    //need to add latest bit to binary_as_a_string
    char digit('0');
    if(i%2 == 1)
    { 
       //need to add a one not a zero to start
      digit = '1';
     }
    binary_as_str = digit + binary_as_a_string;
   //now clever recursive bit
   //do we have a next digit
   if(i > 2)
   {
      //another digit to get call  this function but first need to shift i
      i = i/2;
      GetBinaryString(i, binary_as_string);
   }
}

This function will add a current binary number to string

this is not the only problem though you need to make sure that the string
has the right number of '0's at the start

so

void Print_n_bit_until(int n)
{
 std::string to_print("");
 for(int i = 0; i < n; ++i)
 {
  to_print.clear(); //otherwise to_print will just get longer and longer
  GetBinaryString(i, to_print);
  //now need to ensure to print is n digits add leading 0
 
  for(int j(to_print.size()); j < n; ++j)
  {
     //ie 3 would be 11 and if n is 8 would want 0011
    to_print = '0' + to_print;
   }
  std::cout << to_print << std::endl;
 }
}

This code can be improved
The int &i means that the number can be changed within the
function otherwise it copies the number this is called a reference

My code:

#include<iostream>
#include<string>
using namespace std;

void printAllBitStrings(int n, string binary){
       if (n == 1) /*wrong condition you want to be checking current digit*/{
        cout << "0" << endl;
        cout << "1" << endl;}//adding "01" every time
      else {
        printAllBitStrings(n - 1, binary  );
        binary[n] = '0'; //lucky doesn't blow up check length of binary
        printAllBitStrings(n - 1, binary  );
       //you are not reaching here when you think you are
        binary[n] = '1';
        
     }
} 
    
int main(){
    
    string binary;
    int n;
    cin >> n;
   
    for(int i = 0; i < n; i++){
            binary += "0";
            printAllBitStrings( n, binary);
            cout << endl;
            } 
    return 0;  
}

[Dhanika]

Thank you tetron. You're very helpful. But I managed to find out ( after some discussion with my TAs) on teh best solution. Its simple and quite straightforward too.

This code, uses no loops or arrays or anything. have a look. :D

It was an assignment question by the way. But The deadlines passed.
Cheers!

#include<iostream>
#include<string>
using namespace std;

// function that uses recursion to output the binary numbers
void printAllBitString( int n, string binary){
     if ( n==0 ){
          cout << binary << endl;}
     else{
          
          printAllBitString( n-1, binary + "0" );
          printAllBitString( n-1, binary + "1" );
          ;
          }
}
// start of main function.
int main(){
    string binary="";
    int n;
    cin >> n;// input value to integer n.
    
    printAllBitString( n, binary);
    
    system("pause");
    return 0;
}

[Dave Sinkula]

But I managed to find out ( after some discussion with my TAs) on teh best solution. Its simple and quite straightforward too.

This code, uses no loops or arrays or anything. have a look. :D

[/me builds code and runs it...]

123
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000101
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000110
...
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001010110000110
^C

:icon_lol: Great solution. (Recursion is a form of a loop, BTW.)

[Dhanika]

I know what's the problem. Earlier on I said n bit strings, from 1 to 16 only. It was specified.
Perhaps your '123' was too much, and I tried it myself. There's a possiblity the ones are there, but they start of from the far right, which you probably can't see/ or didn't notice. Try testing with 16, 20 and 50 then 123. :D
So it does print anyways in order, just its fast and alot.

And It works perfectly. :D

Recursion, from what I understand is the repeated process of breaking down a big problem into small parts, till the final part, which is the base case is reached. No?

And I suppose it is indeed a form of a loop. Thanks :)