CODEWITHSUNDEEP
c++recursionvector
Hanna369
Hanna369

Reputation: 61

Recursive function that returns a sum of all elements in a vector

I am confused on how to get this function to add the last element in the vector. I cannot modify the functions parameters.

long vectorSum(const std::vector<int>& data, unsigned int position)
{
   if (position == data.size()-1)
   {
      return 0;
   }
   else 
   {
      return (vectorSum(data, position+1) + data[position]);
   }
}

int main()
{
    //vectorSum test
   std::vector<int> data = { 1,2,3,4,5};
   unsigned int pos = 0;
   std::cout << "expected: 15, " << "actual: " << vectorSum(data, pos) << std::endl;

}

Upvotes: 0

Views: 2730

Answers (3)

Pete Becker
Pete Becker

Reputation: 76245

There are always two parts to a recursive function: a stop condition and a recursion. A simple stop condition here is: when there are no elements in the vector, the sum is 0. The recursion is: the sum of the elements of a non-empty vector is the value of its first element plus the sum of the remaining elements. In code, the stop condition looks like this:

if (position == data.size())
    return 0;

In code, the recursion looks like this:

else
    return data[position] + vectorSum(data, position + 1);

A slightly more sophisticated stop condition would be: when there is exactly one element in the vector, the sum is the value of that element. In code:

if ( position == data.size() - 1)
    return data[position];

Compared to the first one, this has one fewer levels of recursion. But it doesn't work for empty vectors. So pick your poison.

The problem with the original code is that its stop condition isn't implemented correctly. It inter-mixes these two stop conditions.

Upvotes: 1

Steve
Steve

Reputation: 1757

When you're looking at the last element, you have this condition:

if (position == data.size()-1)

At this point, position is 4, and data.size() is 5. So the condition matches and the recursion ends.

You need to change the == to >, or drop the -1

Upvotes: 1

thebenman
thebenman

Reputation: 1621

when you stop at data.size() -1 you are returning 0 for vectorSum(data, data.size()-1) without counting the value of the last entry 

long vectorSum(const std::vector<int>& data, unsigned int position)
{
   if (position == data.size()) // You were stopping early
   {
      return 0;
   }
   else 
   {
      return (vectorSum(data, position+1) + data[position]);
   }
}

int main()
{
    //vectorSum test
   std::vector<int> data = { 1,2,3,4,5};
   unsigned int pos = 0;
   std::cout << "expected: 15, " << "actual: " << vectorSum(data, pos) << std::endl;

}

Upvotes: 3

Related Questions