c++ - 递归算法对数组中每个值小于 x 的元素求和

Question

我是 C++ 的初学者，我正在尝试编写一个递归算法，该算法返回数组中值小于 x 的每个元素的总和。

这是我的代码:

#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;
}

我正在使用 Visual Studio，当我运行代码时，我收到了这个警告:“警告 C4715:'sumOfElement':并非所有控制路径都返回一个值。”程序总是在它要求我停止执行时停止执行输入 x 的整数值。

我的代码有什么问题？

Answer 1

您在这里的方法并不是真正的递归。递归的想法是考虑一个基本情况，然后考虑如何减少每一步的问题，直到达到基本情况。

对于这个问题:

• 基本情况是数组的长度为零。在这种情况下，我们返回的总和为零。 (直觉上:如果数组为空，则我们不添加任何内容，总和为零。)
• 为了减少我们的数组，我们查看数组的最后一个元素(即 lengthOfArray - 1)。我们处理这个元素:如果它小于 x 我们添加它，如果不是那么我们忽略它。然后，我们通过相同的方式(通过调用相同的函数，但使用不同的数组长度)获得处理数组其余部分的结果，并在适用时添加我们的结果。

所以，一些示例代码:

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);
        }
    }
}