How to replace characters of a string in c++ with a recursive function?

Question

Hello I'm a beginner in cpp programming. I was reading some examples of cpp programs and i see this question but i couldn't solve it : There's an algorithm below starting from 0 as each step that goes forward you should replace all 0's with 01 and 1's 10. The input is the number of stage and the output is the number that generates solve this with recursive function.

Here is the example:

1)0
2)01
3)0110
...
Input:3
Output:0110

I tried this:

string generate(string &algorithm, int n) {

    if (n <= 0)
        return algorithm;
      //confused?

}
 
int main() {
    string algorithm = "0";
    string new_algorithm;
    long long int n, k;
    cin >> n >> k;
    new_algorithm = generate(algorithm, n);

    return 0;
}

   

It should be in recursive form but I can't do it straight too! Any help would be appreciated!

Answer 1

The number of recusions is given so the function will look something like this:

std::string replace_recursive(const std::string& in, int n) {
    if (n <= 0) return in;

    std::string next = replace(in);

    return replace_recursive(next,n-1);
}

It has a stop condition, it executes a single step (by calling replace) and it has the recursive call.

All you need to add is going from in to next. For this it is easiest to use a range based loop and construct the new string by appending. I am trying to not give away the whole solution:

std::string replace(const std::string& in) {
     std::string result;
     for (const auto& c : in) {
         if (c == ....) result += " ... ";
         else if (c = ....) result += " .... ";
     }
     return result;
}