尝试递归获取数组元素的总和

Question

我试图在c++上递归地找到数组元素的和。

#include <bits/stdc++.h>
using namespace std;
int findSum(int arr[], int b, int e)
{
if(b == e)
return arr[b];
else
{
int mid = (b + e) / 2;
int x = findSum(arr, b, mid);
int y = findSum(arr, mid, e);
return x + y;
}
}
int main()
{
int arr[] = {1, 6, 3, 10, 11, 4, 5, 9, 15, 2};
cout << findSum(arr, 0, 9);
cout << endl; system("pause");
return 0;
}

运行后，我得到(发生异常。分段故障(

Answer 1

试图在c++中递归地做任何事情都是危险的。Yout程序将面临堆栈溢出的风险，因为它有多个重复的函数填充堆栈，每次调用自己时都会变大。

因此，以下是如何迭代执行：

long int findsum(const int array[], int elementstart, int elementend) {
long int summedArray = 0;
for (int currentcell = elementstart; currentcell <= elementend; ++currentcell)
summedArray += array[currentcell];
return summedArray;
}

Answer 2

您的函数不正确。例如，如果数组只有一个元素，则函数返回0。

除此之外，如果数组包含两个元素，则传递索引b=0，e=1。然后中间的索引等于0((b+e(/2==0(，并且您再次递归调用具有相同值b=0和e=1的函数。所以有一个无限的递归。

您应该将范围指定为[begin index，index after the last]。

但在任何情况下，函数都可以写得更简单。Ywo索引是多余的。

下面是一个演示程序，展示了如何编写函数。

#include <iostream>
long long int findSum( const int a[], size_t n )
{
return 
n == 0 ? 0 
: ( n == 1 ? *a 
: findSum( a, n / 2 ) + findSum( a + n / 2, n - n / 2 ) );
}
int main() 
{
int arr[] = { 1, 6, 3, 10, 11, 4, 5, 9, 15, 2 };
const size_t N = sizeof( arr ) / sizeof( *arr );
std::cout << findSum (arr, N ) << 'n';
return 0;
}

程序输出为

66

Answer 3

问题在代码中的位置已经在弗拉德来自莫斯科。

---

无论如何，这里有一个更简单的递归解决方案来求和集合的元素：

您可以保留一个变量，告诉您当前正在考虑数组的哪个索引，当该索引大于数组的大小时，您可以返回0，即求和的中性元素。

否则，只需将arr[i]与数组的rest之和相加即可。

int findSum(const int arr[], const int i, const int size)
{
if(i > size)
return 0;
return arr[i]+findSum(arr, i+1, size);
}

我发现它对眼睛更容易