String & is not reflecting changes made But String does....while passing arguments?

Question

Question - Given a string a '0', '1' and '?'. Generate all possible strings where you can replace '?' with '0' or '1' ?

For eg - Input - "0??" Output - "000", "001", "010", "011".

I have written a simple program for it -

void gen(string& str, int index)
{
    int i;
    if(str.length() == index)
    {
        cout << str << endl;
        return;
    }
    else
    {
        for(i=index; str[i]!='\0' && str[i]!='?';i++);

        if(str[i] == '?')
        {
            str[i] ='0';
            gen(str,i+1);
            str[i] ='1';
            gen(str,i+1);
        }
    }
    return;
}

int main()
{
    string s ="0??";
    gen(s, 0);
    return 0;
}

It is not working correctly.... BUT IF YOU REPLACE THE ARGUMENT IN void gen(String &, int) to

void gen(String, int)....

THEN IT WILL WORK CORRECTLY..

Can Anyone explain me please....

Answer 1

When you pass the string by reference, there is a single string that is operated on by all of the recursive calls to gen() - instead of each call to gen() working on its own local copy. Each recursive call to gen() modifies the (shared) string, removing all the '?' characters; when that call returns, there are no more '?' characters left to process so it simply terminates.

when you pass the string by value, each invocation of the gen() function gets its own local copy of the string; Any changes it makes to that string are thrown away and forgotten when the function returns to the previous level. In this case your logic is correct.

(There was also a bug which caused it to crash on my Windows machine until I fixed it: std::string is not null-terminated, so rather than checking for std[i] == '\0' you should do something like i < str.length().)

Answer 2

reference will maintain the value changed in the function call

after set str[1] ='0';

sub call: gen(str,2); will output combination: 000 001

reset str[1] ='1';

str is still 011

gen(str,i+1); output nothing 

hope this piece of code can help

#include <string>
#include <iostream>
#include <stdio.h>
using namespace std;
void gen(string& str, int index)
{
    int i;
    if(str.length() == index)
    {
        cout << str << endl;
        return;
    }
    else
    {
        for(i=index; str[i]!='\0' && str[i]!='?';i++);

        if(str[i] == '?')
        {
            printf("before set pos %d to 0: %s\n",i,str.c_str());
            str[i] ='0';
            printf("after set pos %d to 0: %s\n",i,str.c_str());
            gen(str,i+1);
            printf("before set pos %d to 1: %s\n",i,str.c_str());
            str[i] ='1';
            printf("after set pos %d to 1: %s\n",i,str.c_str());

            gen(str,i+1);
        }
    }
    return;
}

int main()
{
    string s ="0??";
    gen(s, 0);
    return 0;
}

it outputs：

Answer 3

One simple solution will be:

As each '?' should be replaced with 0 and 1, we can see that there will be '2 ** (number of ?)' such possible replacement in the string. Eg., if we have three '?' in the string there will be 8 such possible replacement and if we consider their numeric value, they will be 0,1,2...,7 and binary representation of which will be 000,001,002,....,111. Basically we should take the the numeric values and replace the '?'s with the bits from the numeric values.