CODEWITHSUNDEEP
c++recursionvectoriterator
Jarek Danielak
Jarek Danielak

Reputation: 430

C++ sum of vector elements using recursion

I'm trying the following to get the sum of all the elements in the vector. According to the debugger, the inside of if statement is executed but the result is always 0.

double Problem1::recSum(std::vector<double> list) //public
{
    return recSum(list.begin(), list.end(), 0);
}

double Problem1::recSum(std::vector<double>::iterator begin, std::vector<double>::iterator end, double sum) // private
{
    if (begin != end)
    {
        sum += *begin;
        recSum(++begin, end, sum);
    }
    return sum;
}

I know the vector is filled properly cause I calculate the same sum iteratively before. In case I'm misunderstanding recursion horribly, please provide me with some materials on that matter.

Upvotes: 0

Views: 2419

Answers (1)

Pavel P
Pavel P

Reputation: 16843

Because you need to return result of your recursion:

double Problem1::recSum(std::vector<double>::iterator begin, std::vector<double>::iterator end, double sum) // private
{
    if (begin != end)
    {
        sum += *begin;
        return recSum(++begin, end, sum);
    }
    return sum;
}

As a note, your recSum should take const std::vector<double>& list to avoid copying your vector, and, obviously, it would be better to iterate elements than use recursion here. If you want to use recursion, it's probably better to write it this way:

double Problem1::recSum(std::vector<double>::iterator begin, std::vector<double>::iterator end) // private
{
    return (begin != end) ? *begin + recSum(begin+1, end) : 0.0;
}

One other option is to use std::accumulate:

#include <numeric>

double Problem1::recSum(const std::vector<double>& list) //public
{
    return std::accumulate(list.begin(), list.end(), 0);
}

In your case it's quite obvious, because your recSum doesn't have any side effects, and effectively won't make a difference because you do not use its return value. So you always had 0 as a result of your function because first element of your vector was 0. Usually, when you write some algorithm you should try to step trough the code with simple inputs like empty vector, vector with one element, and vector with 2 elements. With 0 and 1 elements it will work, but with 2 elements it will return wrong result. Imagine you had vector of two doubles [0.0, 1.0], on first iteration your sum becomes 0+0.0, and you will recursively call your function with your iterators pointing to the remainder or your sequence: [1.0], second iteration will correctly calculate the sum as 1.0, but then that result isn't used anywhere.

Upvotes: 2

Related Questions