-
October 18th, 2009, 02:18 AM
#1
Recursion function, sum of elements in vector
Hi Code Gurus,
though this is my first post, I've been a peeper for awhile.
I'm trying to write a recursive function that returns the sum of the upper elements of a vector.
Upper meaning, if there are 8 elements total (starting at index 0), then the function will return the sum of the elements in the range, mid (index 4) to (vector.size()-1).
int sum_vec(vector<int> & v, int low, int high)
{
int mid = ((int)v.size()-1) *.5;
if(low == high)
{
return v[high];
}
return sum_vec (v, mid+1, high) + v[low];
}
The main issue is with my mid variable,does not progress the satisfying the base case.
I tried another approach by having the recursion traverse the vector in decreasing order, starting from the last element:
int sum_vec(vector<int> & v, int low, int high)
{
int mid = ((int)v.size()-1) *.5;
if(low == mid)
{
return v[high];
}
return sum_vec(v, high-1,(int)v.size()-1) + v[low];
}
Same issue as the other code attempt. The recursion does not progress to the base case.
Any suggestions would be greatly appreciated. Thanks
-
October 18th, 2009, 08:40 AM
#2
Re: Recursion function, sum of elements in vector
First question is why are you multiplying by 0.5 instead of just dividing by an integer 2? There is no need to introduce floating point calculations just to divide by 2.
Second, have you used the debugger to step through your code?
Your code also has nothing specific to Visual C++. It should be moved to the non-Visual C++ forum by one of the moderators.
Regards,
Paul McKenzie
Last edited by Paul McKenzie; October 18th, 2009 at 08:43 AM.
-
October 18th, 2009, 08:55 AM
#3
Re: Recursion function, sum of elements in vector
thanks for the reply,
I'll change the float entry.
Yes I have used the debugger, that's how I realized that my recursion attempts are not incrementing or decrementing. For instance, if I tried the first code, it would incremet to the 4th index, but continue to run without incrementing, eventually causeing a stack overflow error.
Same for the second code attempt, but it remains on the 6th index.
-
October 18th, 2009, 10:09 AM
#4
Re: Recursion function, sum of elements in vector
int mid = ((int)v.size()-1) *.5;
This line depends only on the whole vector size, this is why current position is not incrementing. This line must contain at least one of function parameters, low or high, to start recursion. I am not sure whether you need to compute mid recursively. Maybe it is better to increment current position by 1, and compute mid only on the first call.
-
October 18th, 2009, 12:40 PM
#5
Re: Recursion function, sum of elements in vector
thanks for the suggestion!
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|