recursive algorithm to sum of every element in an array with a value lesser than x

Question

I'm a beginner to c++ and I'm trying to write an recursive algorithm that returns the sum of every element in an array with a value less than x.

Here is my code:

#include <iostream>

using namespace std;

int sumOfElement(int xList[],int x, int lengthOfArray){
    int  sum = 0;
    if (lengthOfArray == 0)
        return sum;
    else
        for (int i=0; i <= lengthOfArray; i++) {
            if(xList[i] < x)
                return sum + xList[i];
            else
                sumOfElement(xList,x,lengthOfArray-1);
    }
}


int main() {
    cout << "Size of Array: ";
    int size; 
    cin >> size;
    int *xList = new int[size];

    //Inputing array.
    cout << "Enter elements of array followed by spaces: ";

    for (int i = 0; i<size; i++)
        cin >> xList[i]; 

    cout << "Enter the integer value of x: " <<endl;
    int limit;
    cin >> limit;

    cout << "Sum of every element in an array with a value less than x: " << sumOfElement(xList,limit,size) << endl;

    return 0;
}

I'm using Visual Studio, while I was running the code, I got this warning: "warning C4715: 'sumOfElement' : not all control paths return a value. " And the program always stop executing when it asks me to enter the integer value for x.

What's wrong with my code?

Answer 1

Your approach here isn't really recursive. The idea with recursion is to consider a base case, and then consider how to reduce the problem at each step until you get to the base case.

For this problem:

• The base case is when the length of the array is zero. In this case we return a sum of zero. (Intuitively: if the array is empty then we're adding nothing, giving a sum of zero.)
• In order to reduce our array we look at the last element of the array (ie. at lengthOfArray - 1). We process this element: if it's less than x we add it, if it's not then we ignore it. We then get the result of processing the rest of the array by the same means (by calling the same function, but with a different array length), and add our result if applicable.

So, some example code:

int sumOfElement(int xList[], int x, int lengthOfArray){
    if (lengthOfArray == 0) {
        // base case
        return 0;
    } else {
        int value = xList[lengthOfArray-1];
        if (value < x) {
            // process the rest of the array and add our result
            return value + sumOfElement(xList, x, lengthOfArray - 1);
        } else {
            // process the rest of the array
            return sumOfElement(xList, x, lengthOfArray - 1);
        }
    }
}

Answer 2

for (int i=0; i <= lengthOfArray; i++)
{
    if(xList[i] < x)
        return sum + xList[i];
    else sumOfElement(xList,x,lengthOfArray-1);
}

You shouldn't have a for-loop, and recursive functions should "return" the deeper call, so

int retVal = 0;
if(xList[lengthOfArray-1] < x)
    retval = xList[lengthOfArray-1]
return retVal + sumOfElement(xList,x,lengthOfArray-1);