使用递归算法计算数组中所有小于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，运行代码时出现了这个警告：“warning C4715：'sumOfElement'：不是所有控制路径都返回值。” 而当程序要求我输入整数x时，程序总是停止执行。

我的代码有什么问题吗？

- user59036

---

if (lengthOfArray = 0)看起来不太对。 翻译：这段代码的条件语句应该是在判断lengthOfArray是否等于0，而不是将其赋值为0。正确的写法应该是if (lengthOfArray == 0)。 - Blender

for 循环是迭代的一个例子，而不是递归。它们之间有严格的等价关系，但它们并不相同 - 它们可以实现相同的最终结果，但是使用不同的方式进行操作。递归没有显式的循环 - 它具有调用自身的函数（可能是通过其他函数间接调用）。 - user180247

Answer 1

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

你不应该使用for循环，递归函数应该“返回”更深层次的调用，因此

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

- Mats Petersson

---

那么，如果您不再有循环，您的“i”从哪里来呢？另外，sum + xList[i]如何处理数组的其余部分？ - mange

已进行编辑以删除使用“i”。 - Mats Petersson

仍然不正确，因为你的 xList[lengthOfArray-1] < x 仍然没有处理数组的其余部分。使用你的更改，sum 永远不会被设置为除零以外的任何值。 - mange

Answer 2

你这里的做法并不是真正的递归。递归的思想在于考虑一个基本情况，然后考虑每一步如何缩小问题，直到达到基本情况为止。

对于这个问题:

• 基本情况是数组长度为零时，我们返回零的和。(直观上来说: 如果数组为空，则我们相加的数为零，结果为零)。
• 为了缩小数组，我们看看数组的最后一个元素(即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);
        }
    }
}

- mange

---

为了使用尾递归，我会这样做：value = (value < x) ? value : 0; return value + sumOfElement(xList, x, lengthOfArray - 1); - Eugene

@Eugene 这不是尾递归。这是尾递归模cons。我的函数实际上更加尾递归（我的第二个else分支是尾递归，而“value < x”情况是尾递归模cons）。无论哪种方式：在理解递归的这个层面上，我不会深入讨论尾递归。（对于真正的尾递归，我们需要一个累加器。） - mange