Segmentation fault with recursion

Question

I'm trying to write C++ code for solving house-robber problem.

But my recursion doesn't work, I'm getting Segmentation fault. Can't understand what's wrong. Please, take a look

int award(vector<int>& nums, int n, vector<int>& sum)
{
    if (n == 0) sum[0] = 0;
    if (n == 1) sum[1] = nums[0];
    if (n > 1) 
    {
        if ((sum[n-1]) < 0) sum[n-1] = award(nums,n-1,sum);
        if ((sum[n-2]) < 0) sum[n-2] = award(nums,n-2,sum);
        sum[n] = max(sum[n-2] + nums[n-1], sum[n-1]);
    }
    int ans = sum[n];
    return ans;
}

int main() 
{
    vector<int> nums;
    vector<int> sum (100); 
    int a;
    int i = 0;
    while (cin>>a)
    {
        nums[i] = a;
        i++;
    }
    int n = nums.size();
    for(int i = 0; i <= n; i++)
    {
        sum[i] = -1;
    }
    cout<<award(nums,n, sum);
}

nums has no size, so nums[i] for any value of i is out of bounds. One generally uses push_back when there will be an unknown number of items to put in the vector. — crashmstr
– crashmstr, Commented May 10, 2016 at 12:14
Also note: learn to use your debugger and it can help you find the exact line of where the error is generated. — crashmstr
– crashmstr, Commented May 10, 2016 at 12:19
thanks, you're right about push_back, I missed that while interpreting the code to make vector input. Now It works — Helen_M
– Helen_M, Commented May 10, 2016 at 13:43

Michael Burge · Accepted Answer · 2016-05-10 12:15:37Z

3

Let n = nums.size(). One problem is that your for loop is running from 0 to n, which is actually n+1 integers in a collection of size n. So one of them is out-of-range(and it is nums[n]).

An example: If n = 3, then 0,1,2,3 is a collection of 4 integers not 3.

answered May 10, 2016 at 12:15

Michael Burge

4659 silver badges16 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Helen_M Over a year ago

I call for nums[n-1] instead of nums[n]

A. Ocannaille Over a year ago

for(int i = 0; i <= n; i++) should be for(int i = 0; i < n; i++) Otherwise you try to access an unexistant memory case

Collectives™ on Stack Overflow

Segmentation fault with recursion

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related