Alter a function to use Recursion

[gretty]

Hello

I have just learnt recursion & I thought I would try & alter some of my previous funtions to make them recursive, well the 1st function I try to alter totally stumps me & I thought I understood recursion :P

Is it possible to make this function recursive?

int findSum (vector < int > v)
{
	int sum = 0
	
	for (int i=0; i<v.size(); i++) {
	   sum += v.at(i);
	   }
	   
	return sum;
}

I am trying to get the function to find and return the sum of all elements in a vector

[Nick Evan]

Is it possible to make this function recursive?
[..]
I am trying to get the function to find and return the sum of all elements in a vector

My rule of thumb is: "If it has loops, it can be made recursive"

Since this isn't homework (I hope), here's how I'd do it. I've put some comments in it so that you can understand what I'm doing. Note that this is not the only (or maybe best) way to do it.

void findSum (vector < int > v, int *sum)
{
    *sum += v.at(v.size()-1); // add the last element to the sum
    v.pop_back(); // remove last element
    if (!v.size()) return; // If the vector is empty
    else findSum(v, sum); // recursion
}

int main(){
    vector<int> testvec;
    // test values
    testvec.push_back(1);
    testvec.push_back(3);
    testvec.push_back(7);
    testvec.push_back(19);
    int sum = 0;
    findSum(testvec, &sum); // pass by reference
    cout << sum;
    cin.get();
    return 0;
}

If you have any questions, don't hesitate to ask!

[wilch]

Well, you can try this:

int findSum (vector < int > v){
  int sum = 0;
  if(v.size() <= 0) return 0;
  else{
      position = v.size() - 1;
      sum += v.at(position);
      v.remove(position); //need to have this function/similar in the vctr
     return findSum(v);
  }
}

[Nick Evan]

Well, you can try this:

Well you could, but it won't work. Position is undefined, and I've never heard of a member for vector that's called remove() And even if you correct these errors, this line: if(v.size() <= 0) return 0; will make the function always return 0; when it's done.

Lesson learned: test first, post later :)

[mrnutty]

another example :

typedef float data_type; 

data_type mySumRecursive(vector<data_type> vec, data_type * s,int strt = 0)
{
	if(strt == vec.size())
		return vec[strt-1]; 

	 *s +=  vec[strt];

	 mySumRecursive(vec,s,strt+1);
}

[Tom Gunn]

I think a more important question than how to make a function recursive is why should it be recursive? Recursion is great, but it has pitfalls. If the recursion goes too deep, you risk a stack overflow with no way to intercept the exception. Hard crashes like that are very very bad.

The best use of recursion when it makes a complex iterative algorithm shorter and easier to understand. If the difference between iterative and recursive is minimal, there is no reason to add the risks and potential inefficiencies of recursion. Compare and contrast:

int FindSumIterative(vector<int> const& v)
{
    int sum = 0;

    for (int x = 0; x < v.size(); ++x) sum += v.at(x);

    return sum;
}

int FindSumRecursive(vector<int> const& v, int x=0)
{
    if (x == v.size()) return 0;

    return v.at(x) + FindSumRecursive(v, x+1);
}

Both functions do the same thing, are called the same way, and have the same result with the same amount of code complexity. But the iterative version is safer for large vectors because the recursive version can cause a stack overflow. It might also be inefficient because of overhead from calling functions and storing all of the stack frames in memory.

There is no benefit to using recursion because the iterative algorithm is just as simple and much safer for a linear algorithm. A better use of recursion is for something like quicksort where the iterative algorithm is much more complex than the recursive one, and for a good pivot strategy where the number of function calls is closer to log(n) than n. Linear algorithms are not good candidates for recursion unless you can guarantee that n will be small.