Recursion in c++ (generate binary codes)

Question

I am trying to write a program that generates all the binary codes given an input number (for the number of bits). For example, if the user inputs 3, it should generate all the numbers below:

The function is called generateBinaryCode(), and it has to be recursive (that's the challenge of the question).

The following is my attempt but it doesn't work. Can anyone please offer me some insights?

Thanks in advance.

#include <iostream>
#include <string>
#include <vector>

using namespace std;
vector<string> generateBinaryCode(int nBits);

int main()
{
    int input;

    while (true)
    {
        cout << "Enter an integer (any negative numbers are sentinel): ";
        cin >> input;
        if (input < 0) break;

        for (unsigned i = 0; i < generateBinaryCode(input).size(); i++)
            cout << generateBinaryCode(input).at(i) << endl;
    }

    return 0;
}

vector<string> generateBinaryCode(int nBits)
{
    vector<string> result;
    int size = result.size();
    std::vector<string>::iterator it;

    if (nBits == 1) {

        result.push_back("0");
        result.push_back("1");

    } else {
        result = generateBinaryCode(nBits - 1);

        for (unsigned int i = 0; i < result.size(); i++)
        {
            result.push_back("0" + result.at(i));
            result.at(i) = "1" + result.at(i);
        }

    }

    return result;
}

Can someone do this using pure recursion, no loops, no return value, it just prints, and take one integer argument, the number n, — Manjunath, Jul 16 '18 at 13:37

NPE · Answer 1 · 2013-09-20T14:45:57.390

The main flaw is in the following loop:

    for (unsigned int i = 0; i < result.size(); i++)
    {
        result.push_back("0" + result.at(i));
        result.at(i) = "1" + result.at(i);
    }

In a nutshell, you don't want to be adding elements to result while iterating over it. What you have right now is an infinite loop (that'll eventually run out of memory).

Also, you don't want to be calling generateBinaryCode() at every iteration of your main loop. Call it once and store the result in a variable.

And finally (and least importantly), entering 0 at the prompt will result in infinite recursion.

score 1 · Accepted Answer · answered Sep 20 '13 at 15:43

Your code is very close to correct, but the self-modifying result is going to be problematic. insertion into a vector does many things, among them invalidating iterators currently open on the sequence. But it will also change the result of size() (for obvious reasons, I hope).

The simplest answer is to use a sub list vector, then enumerate that, appending all entries within with '0' and '1', and inserting those results into your return vector. An example of this is below:

std::vector<std::string> getBitStrings(unsigned int n)
{
    std::vector<std::string> result;

    if (n <= 1)
    {
        result.push_back("0");
        result.push_back("1");
    }
    else
    {   // recurse, then add extra bit chars
        std::vector<std::string> sub = getBitStrings(n-1);
        for (std::vector<std::string>::const_iterator it = sub.cbegin();
             it != sub.cend(); ++it)
        {
            result.push_back(*it+'0');
            result.push_back(*it+'1');
        }
    }
    return result;
}

This is somewhat different than your implementation, in that it expects values between 1 and n for the bit count. Running with n=5, the following is produced:

int main()
{
    std::vector<std::string> bs = getBitStrings(5);
    std::copy(bs.begin(), bs.end(), 
         std::ostream_iterator<std::string>(std::cout, "\n"));
    return 0;
}

Output

To be honest there are a plethora of ways this can be done, this is just one. I purposely modeled it after your original implementation so as to limit algorithm change. I hope it helps you understand the problem and one way around it.

Is there any reason why const_iterator is used instead of a normal iterator? — Roy, Sep 20 '13 at 16:27

score 1 · Answer 3 · answered Jun 04 '17 at 06:31

simpler and concise solution

void printBin(std::string prefix, int n)
{
    if(prefix.size() == n)
    {

        std::cout <<prefix <<std::endl;
        return;
    }

    printBin(prefix + '0', n);
    printBin(prefix + '1', n);

    return;

}

int main()
{
    int n;
    std::cin >> n;
    printBin("", n);
    return 0;
 }

score 0 · Answer 4 · edited May 23 '17 at 12:11

0

What you are trying to do at this line

result.push_back("0" + result.at(i));

is basically this, and that may be dodgy, and cause of your problem.

edited May 23 '17 at 12:11

Community

1
1

answered Sep 20 '13 at 14:46

BЈовић

62,405
41
173
273

score 0 · Answer 5 · answered Sep 20 '13 at 14:59

Here's a simple one:
(written in C, not C++, but the outline should be the same)

void generateBinaryCode(char* txt, int i, int len)
{
    if (len != 0)
    {   txt[i] = '0';
        makeBinary(txt, i+1, len-1);

        txt[i] = '1';
        makeBinary(txt, i+1, len-1);
    } else
    {
        puts(txt);
    }
}


int main()
{
    char str[4] = {0};

    generateBinaryCode(str, 0, sizeof(str)-1);

    getchar();
    return 0;
}

Recursion in c++ (generate binary codes)

5 Answers5