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

The easiest way to think of recursion is that you're going to do something for the first element of a set of data (so the first character of a string, for example), then you're going to do it again to the remainder of the data. Break up the problem like that- first get it working for 1 element, then find a way to call it on the rest of the data. — Gabe Sechan
– Gabe Sechan, Commented Mar 16, 2021 at 18:19

Andrei Pangratie · Accepted Answer · 2021-03-16 18:46:46Z

4

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

answered Mar 16, 2021 at 18:46

Andrei Pangratie

713 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

masonCherry Over a year ago

the other problem was also trying avoid a performance hit with many constructor calls.

Andrei Pangratie Over a year ago

I don't think OP cares about that given the task of writing it using recursion(assuming an useful use of recursion for the problem) and not changing the function signature.

463035818_is_not_an_ai · Accepted Answer · 2021-03-16 18:26:38Z

1

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.

edited Mar 16, 2021 at 18:26

answered Mar 16, 2021 at 18:22

463035818_is_not_an_ai

129k11 gold badges116 silver badges240 bronze badges

23 Comments

SergeyA Over a year ago

This is correct from algo point of view, but terrible from performance point of view. All those copies of strings which would be made... It is also not TCO friendly.

463035818_is_not_an_ai Over a year ago

@SergeyA ups, forgot references, though even without the copies this might cause a stackoverflow for long strings when a loop is much simpler and has no such issues

masonCherry Over a year ago

@ChrisDodd Tail Call Optimization

Michele Over a year ago

Thank you all for your help!

463035818_is_not_an_ai Over a year ago

@MrBrN197 Don't get me wrong, I am not the he/she police ;). Using "they" is a nice way to not be wrong always.

|

masonCherry · Accepted Answer · 2021-03-16 18:42:03Z

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

biqarboy · Accepted Answer · 2021-03-16 19:02:15Z

0

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

answered Mar 16, 2021 at 19:02

biqarboy

8626 silver badges15 bronze badges

2 Comments

Loki Astari Over a year ago

Could be more efficient. As soon as one parameter reaches zero length simply return the other as the result. If you do that you no longer need to check the size of the parameters before checking because we will know that both will always be greater than zero size.

biqarboy Over a year ago

Yes, that would possible.

Loki Astari · Accepted Answer · 2021-03-16 19:08:11Z

#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");
}

Collectives™ on Stack Overflow

Creating a recursion in c++

5 Answers 5

2 Comments

23 Comments

Comments

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

2 Comments

23 Comments

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related