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

## Recommended Answers

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 …

## All 4 Replies

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

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

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

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 :)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.21 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.