Creating a recursion in c++

Question

I'm learning how to write recursions, and I am confused as to how to simplify the body of a function into a recursion.

For my current assignment, I have "to Mesh two strings by alternating characters from them. If one string runs out before the other, just pick from the longer one. For example, mesh("Fred", "Wilma") is "FWrieldma". Use recursion. Do not use loops."

Well... I created the loop....

string result;
for (int i = 0; i < a.size(); ++i)
{
    result += a.at(i) + b.at(i)
}

But making that into a recursion is stumping me.

This is what I have so far (We are not allowed to change anything above or below where it is marked):

#include <string>
using namespace std;

/**
   Combines alternate characters from each string.
   @param a the first string.
   @param b the second string
*/
string mesh(string a, string b)
{
// INSERT CODE BENEATH HERE
     string result;
     if (a.size() < 1) result = b;
     if (b.size() < 1) result = a;
     else
     {
        result = a.at(0) + b.at(1);
     }
return result;
// ENTER CODE ABOVE HERE
}

But i know its not right because there is no recursion and it flat out doesn't work

Answer 1

I think this does what you've asked and keeps the function prototype intact. Also it looks similar to your suggested code.

#include <iostream>

using namespace std;

string mesh(string a, string b) {
    if (!a.size()) return b;
    if (!b.size()) return a;
    return a[0] + (b[0] + mesh(a.substr(1), b.substr(1)));
}

int main(int argc, char const *argv[])
{
    printf("%s\n", mesh("Fred", "Wilma").c_str());
    return 0;
}

Answer 2

First try to find out what is a single step of the recursion. There is more than one way to do it, one possibility is traverse the strings by using some index pos and in a single step add the characters from the respective positions of the strings:

std::string mesh(const std::string& a, const std::string& b,size_t pos) {

    /*...*/

    std::string result;
    if (pos < a.size()) result += a[pos];
    if (pos < b.size()) result += b[pos];

    /*...*/
}

To recurse we call the method again for the next index and append to result:

std::string mesh(const std::string& a, const std::string& b,size_t pos = 0) {

    /*...*/
    
    std::string result;
    if (pos < a.size()) result += a[pos];
    if (pos < b.size()) result += b[pos];

    return result + mesh(a,b,pos+1);
}

Finally we need a stop condition. The recursion should stop when both strings have no more characters at index pos:

std::string mesh(const std::string& a, const std::string& b,size_t pos = 0) {

    if (pos >= a.size() && pos >= b.size()) return "";
    
    std::string result;
    if (pos < a.size()) result += a[pos];
    if (pos < b.size()) result += b[pos];

    return result + mesh(a,b,pos+1);
}

For example:

int main() {
    std::cout << mesh("Fred","Wilma");
}

will result in the desired FWrieldma output.

Disclaimer: As pointed out by SergeyA, I didn't pay to much attention to performance when writing this answer. I suppose this is an exercise to practice recursion, while in reality I don't see a reason to implement this via recursion.

Answer 3

Just adding onto largest_prime_is_463035's answer. If you have to keep signature of mesh the same then you would create another function that has the actual implementation and now mesh can be called be only the two string arguments.

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

/**
   Combines alternate characters from each string.
   @param a the first string.
   @param b the second string
*/

void meshInternal(const string a, const string b, string& result, unsigned int index=0){
    if(index >= a.size()){
        result += b.substr(index);
        return;
    }
    if(index >= b.size()){
        result += a.substr(index);
        return;
    }

    result.push_back(a[index]);
    result.push_back(b[index]);
    meshInternal(a, b, result, ++index);
}

string mesh(const string a, const string b)
{
    string result = "";
    meshInternal("Fred", "Wilma", result);
    return result;
}

int main() {
    string result = mesh("Fred", "Wilma");
    std::cout << result << std::endl;
    return 2;
}

Answer 4

As it is not possible to pass another parameter in the mesh function, but in every recursive call we need to know which character from string a and string b will be appended to the result. One simple solution may be removing the first character from both string a and string b and append it to the result. Now, as we are passing string a and string b as reference, removing first character will ultimately make the string empty after a while. So, we can check whether both the string a and string b become empty and set it as the base-case of the recursion call.

This code solves the problem:

std::string mesh(string& a, string& b) {

    if (a.size() == 0 && b.size() == 0) return "";
    
    std::string result;
    if (a.size()) {
        result += a[0];
        a.erase(0, 1);
    }
    if (b.size()) {
        result += b[0];
        b.erase(0, 1);
    }

    return result + mesh(a,b);
}

int main()
{
    string a = "Fred";
    string b = "Wilma";
    std::cout << mesh(a,b);

    return 0;
}

Answer 5

#include <string>
#include <iostream>
#include <string_view>

// recursive mesh function.
// passing the result object for effeciency.
void mesh(std::string& result, std::string_view l, std::string_view r)
{
    // check the exit condition.
    // If either the left of right are empty add the other to the result.
    if (std::begin(l) == std::end(l)) {
        result += r;
        return;
    }
    if (std::begin(r) == std::end(r)) {
        result += l;
        return;
    }

    // Add letter from the left and right to the result.
    result += *std::begin(l);
    result += *std::begin(r);

    // Adjust the size of the view
    l.remove_prefix(1);
    r.remove_prefix(1);

    // recursively call to get the next letter.
    mesh(result, l, r);
}

// Utility wrapper to get view of strings and create
// the result object to be passed to the recursive function.
std::string mesh(std::string const& l, std::string const& r)
{
    std::string result;
    mesh(result, std::string_view(l), std::string_view(r));
    return result;
}

int main()
{
    std::cout << mesh("Fred", "Wilma");
}