Recursion function, sum of elements in vector
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5

Thread: Recursion function, sum of elements in vector

  1. #1
    Join Date
    Oct 2009
    Posts
    37

    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

  2. #2
    Join Date
    Apr 1999
    Posts
    27,446

    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 09:43 AM.

  3. #3
    Join Date
    Oct 2009
    Posts
    37

    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.

  4. #4
    Join Date
    Jul 2002
    Posts
    2,526

    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.

  5. #5
    Join Date
    Oct 2009
    Posts
    37

    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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center