Mapping a function onto a vector recursively

Question

I have a class called mapTriple that has a method that takes an integer vector and multiplies all the values in vector by a private function of the mapTriple class (the function takes an int, and returns the int *3)

I have already set up the classes and the function that triples the integer. I am stuck on the mapTriple method. The method cannot be iterative, it must be recursive.

vector<int> MapTriple::map(vector<int> myVector)
{
    if(myVector.size() == 1)
    {
        myVector[0] = f(myVector[0]);
        return myVector;
    }
    else
    { 
        map(myVector.erase(myVector.begin()+myVector.size()-1));
        myVector[myVector.size()-1] = f(myVector[myVector.size()-1]);
        return myVector;
    }

}

int f (int a)
{
    return (a*3);
}

It currently isnt compiling, it is say there is no matching call to map. I have all the .h files and main files etc

For the record, `myVector.begin()+myVector.size()` is exactly `myVector.end()`, and `myVector[myVector.size()-1]` is `myVector.back()`. — Max Langhof, Jan 25 '19 at 10:02
*"The method cannot be iterative, it must be recursive."* Why? There's no reason to it with recursion when you can just do it with `for (int &a : myVector) a *= 3;` — Blaze, Jan 25 '19 at 10:04
its a homework question for uni and it says it has to be recursive — Juan Pablo, Jan 25 '19 at 10:06
What's the uni's course? "Writing needlessly complicated code?" Anyway, if you really need to do recursion, do a loop from `0` to `myVector.size()-1` and multiply the respective value with `3`, but instead of doing a `for` loop like one normally would, pass the reference to `myVector` and the iterator through recursive calls. — Blaze, Jan 25 '19 at 10:12
@Blaze Worse still the STL has `std::transform` already, although I doubt it's implemented recursively since there really is no need for that. Still, that is a very unusual course indeed. — Qubit, Jan 25 '19 at 10:17

Max Langhof · Accepted Answer · 2019-01-25T10:23:46.240

erase does not return the modified vector. It returns an iterator after the removed element (which will be end in your case, so you don't need that). Just pass the modified vector itself.

You currently don't re-add the erased element, so even if your code compiled, you would always be returning a vector of length 1 (and the remaining element would be tripled n times if the vector was originally size n).

The correct else branch should be:

else
{
    // Store and remove the last element.
    int currentElement = myVector.back();
    myVector.erase(myVector.end()-1);
    // Recursively process the remaining elements.
    map(myVector);
    // Process and re-add the above element.
    myVector.push_back(f(currentElement));
    return myVector;
}

However, instead of erasing elements and re-adding them, you could work with the iterators.

using Iterator = std::vector<int>::iterator;

void MapTriple::map(Iterator start, Iterator end)
{
    // No elements remaining?
    if (start == end)
      return;

    // Process first element.
    *start = f(*start);

    // Process remaining elements recursively.
    map(start+1, end);
}

While this is pretty elegant, it would of course be even simpler to do this with a simple for loop:

for (auto& e : myVector) e = f(e);

or std::transform:

std::transform(myVector.begin(), myVector.end(), myVector.begin(),
               [this](int e) -> { return f(e); });`

It should also be noted that map is probably a mediocre name for this method, if you did using namespace std; as seems to be the case (see also Why is "using namespace std" considered bad practice?).

thanks for the answer, I used the top bit and it didnt work but switched to pointers with the vectors and it seemed to work. Yeah I didnt give it the name map, just took it straight for the question from uni as they have to have specific signatures to pass the web submission. I've never seen iterators before, I am sure I'll learn about them at some stage — Juan Pablo, Jan 25 '19 at 10:23

Mapping a function onto a vector recursively

1 Answers1