What is wrong with this C++ recursion function of mine?

Question

first off sorry if the code comes out weird. Looks good after following the instructions for sharing here but it's my first time. Anyways, I have a class assignment where I need to create a recursive function that when given an array returns the sum of it's elements. I have found solutions that work online but they seem similar enough to mine. My code runs but the sum comes out as a giant integer, specifically with the code below the output of sum is -858993459. I've seen some similar things before and I tried going over what might be a common mistake but I at least failed to find anything. Please help explain what is going on, I would like to use the parameters I've set (I've seen it other ways as stated) because I want my code to be at least somewhat unique. Thanks in advance everyone!

    #include <iostream>
    #include <array>
    #include <string>
    using namespace std;

    int getSumOfElements(int intArray[], int firstElement, int lastElement, int sum) {
    if (firstElement > lastElement)
        return sum;
    else {
        sum += intArray[firstElement] + intArray[lastElement];
        getSumOfElements(intArray, firstElement + 1, lastElement - 1, sum);
        }
    }

    int main()
    {
        int sum = 0, lastElement, firstElement = 0;
        int exampleArray1[] = { 1, 5, 6, 12, 7 }, exampleArray2[] = { 3, -5, -16, 4, 10, 1, 7 };

        lastElement = sizeof(exampleArray1) / sizeof(exampleArray1[0]);
        sum = getSumOfElements(exampleArray1, firstElement, lastElement, sum);
        cout << "The sum of all elements in Array1 are " << sum << endl;

        lastElement = sizeof(exampleArray2) / sizeof(exampleArray2[0]);
        sum = getSumOfElements(exampleArray2, firstElement, lastElement, sum);
        cout << "The sum of all elements in Array2 are " << sum << endl;

        system("pause");
   }

Answer 1

I know that you have made modifications to your question since you initially asked it, but try to leave your question as is for now.

There are a couple problems with your recursive function (original below):

int getSumOfElements(int intArray[], int firstElement, int lastElement, int sum) {
if (firstElement > lastElement)
    return sum;
else if (firstElement == lastElement)
    sum += firstElement;
else {
    sum += intArray[firstElement] + intArray[lastElement];
    getSumOfElements(intArray, firstElement + 1, lastElement - 1, sum);
    }
}

In its simplest form, there are two main things with recursion: the base case, and the recursive case. You have 2 base cases (which is fine):

1. When you are currently in a situation where your firstElement index is greater than your lastElement index (done with even sized array)
2. When your firstElement index is the same as your last element index (done with odd sized array)

The only time you should be doing the actual logic is in the recursive case. Therefore, your base cases should simply be returning 0 (for the first), or intArray[firstElement] (the value) for the second. Why? Because your function only returns the sum of the integers from firstElement to lastElement. If you've crossed, then you've already added all the numbers. If that index is the same, then the sum is just the value itself since that's the only one you still need to add in.

You only do the addition in the recursive case. What you are trying to say is that getSumOfElements(..., first, last, sum) is the same as intArray[first] + intArray[last] + getSumOfElements(..., first+1, last-1, sum) (add the ends and recursively add the rest by doing it again, always getting closer to the middle). Therefore, your recursive case should simply add the value in the array's firstElement index, the array's lastElement index, and the sum of the rest of the values, and return it.

A fixed version would look something like:

int getSumOfElements(int intArray[], int firstElement, int lastElement) {
    if (firstElement > lastElement) {
        return 0;
    }
    if (firstElement == lastElement) {
        return intArray[firstElement];
    }
    else {
        return intArray[firstElement] + intArray[lastElement] + getSumOfElements(intArray, firstElement + 1, lastElement - 1);
    }
}

Notice that you don't need to carry the sum through the recursive calls since you are returning the sum so far in each call. I really hope that sheds some more understanding on recursion.

Working sample: http://ideone.com/9xkMqT

Answer 2

Thanks to all the help above ^^ All comments led to the answer but I unfortunately couldn't choose more than one. However, I reedited my original question to be as it was when first asked and below I will show the working code thanks to all the input.

    int getSumOfElements(int intArray[], int firstElement, int lastElement, int sum) {
        if (firstElement > lastElement)
            return sum;
        else if (firstElement == lastElement) {
            sum += intArray[firstElement];
            return sum;
        }
        else {
            sum += intArray[firstElement] + intArray[lastElement];
            return getSumOfElements(intArray, firstElement + 1, lastElement - 1, sum);
        }
    }

    int main()
    {
        int sum1, sum2, sum3, lastElement, firstElement = 0;
        int exampleArray1[] = { 1, 5, 6, 12, 7 }, exampleArray2[] = { 3, -5, -16, 4, 10, 1, 7 },
            exampleArray3[] = { 1, 3, 5, 6 };

        lastElement = sizeof(exampleArray1) / sizeof(exampleArray1[0]) - 1;
        sum1 = getSumOfElements(exampleArray1, firstElement, lastElement, 0);
        cout << "The sum of all elements in Array1 are " << sum1 << endl;

        lastElement = sizeof(exampleArray2) / sizeof(exampleArray2[0]) - 1;
        sum2 = getSumOfElements(exampleArray2, firstElement, lastElement, 0);
        cout << "The sum of all elements in Array2 are " << sum2 << endl;

        lastElement = sizeof(exampleArray3) / sizeof(exampleArray3[0]) - 1;
        sum3 = getSumOfElements(exampleArray3, firstElement, lastElement, 0);
        cout << "The sum of all elements in Array3 are " << sum3 << endl;

        system("pause");
    }

Answer 3

You are not returning anything in else conditions of you getSumOfElements, it that case garbage value used for return.

Answer 4

You are indexing outside the array.

int lastElement = sizeof(exampleArray1) / sizeof(exampleArray1[0]);
sum = getSumOfElements(exampleArray1, firstElement, lastElement, sum);

And then you do

sum += intArray[firstElement] + intArray[lastElement];

During the first call lastElement will index outside the array. You should do

sum = getSumOfElements(exampleArray1, firstElement, lastElement - 1, sum);

That's why you get a "weird" integer value like -858993459.