我正在尝试使用递归对给定数组中的数字求和，尝试了这段代码，但它不起作用。为什么？

Question

#include <iostream>

   using namespace std;

   int sumByRecursion( int arr[]) {
        int sum = 0;
        int n = sizeof(arr)/sizeof(arr[0]);
        //n is the size of the array
        if (n == 0) {
            return sum;
        } else {
            n -= 1;
            for (int i=0;i=n;++i){
                arr[i]=arr[i+1];
            }
            return (sum + arr[0] + sumByRecursion( arr));
        }
    }

   int main() {
        int arr[]={2, 4, 6};
        sumByRecursion( arr);

        return 0;
    }
    

sumByRecursion 基于这个想法工作： 1-如果数组的大小为0“空数组”，return求和。 2-如果大小不为 0“数组不为空”，对 sum 上的第一个元素求和，然后调用函数，将数组的大小减 1，对新数组进行 sumByRecursion。

Answer 1

您需要将数组的大小传递给 sumByRecursion 例程。

您需要传递数组大小的原因是数组不跟踪自己的大小。

std::array 和 std::vector 等替代方法提供了查询它们大小的能力，但 C 风格数组不携带该信息。

std::size 函数查询 type（在该上下文中是 C 样式数组）以计算大小。一旦作为 int arr[] 参数传递，该 arr 类型为 int*，不再可以生成大小信息。

int arr[]参数是int* arr的一种写法，但是向reader建议arr参数是C风格的数组。如果正确完成，可以被认为是自我记录的代码——但许多程序会将参数表示为 int* arr，所以，唉，这不是一个普遍的习语。

#include <cstddef>
#include <iterator>
#include <iostream>

using std::cout;
using std::size;
using std::size_t;

namespace {

int sumByRecursion(int arr[], size_t n) {
    if (n == 0) {
        return 0;
    } else {
        // Many C++ compilers do not perform tail recursion optimization.
        // But for those that do, this will thwart tail recursion optimization.
        return arr[0] + sumByRecursion(arr+1, n-1);
    }
}

} // anon

int main() {
    int arr[] = {2, 4, 6};
    auto arr_size = size(arr);
    auto sum = sumByRecursion(arr, arr_size);
    cout << sum << "\n";
}

Answer 2

一个（可悲的）常见错误：

int sumByRecursion( int arr[] )
{ // What do you think  ^^^^^  this is?

    int n = sizeof(arr)/sizeof(arr[0]);
    //      ^^^^^^^^^^^ Sorry, too late.
    // ...
}

如评论部分所述

Inside the function the parameter arr has decayed to type int* and knows nothing about the number of elements in the array. ()

In short: int sumByRecursion( int arr[]) is exactly the same as int sumByRecursion( int *arr). That [] syntax in the parameter list is nothing more than syntax sugar. ()

解决方案是将大小与指针一起传递，显式地作为单独的函数参数或在对象内部传递，例如 std::span or std::ranges::range.

当然，另一种方法是传递 std::cbegin() and std::cend() 返回的一对迭代器。

---

用于“将数组的大小减少 1”的代码 可能是同样误解的结果：

int sum = 0;
// ...
if (n == 0) {              // Ok...
    return sum;
} else {
    n -= 1;                // Okayish...
   
    for (int i=0;i=n;++i){ // 
        arr[i]=arr[i+1];   // <-- There's NO need to do all those copies!
    }                      // 

    return (sum + arr[0] + sumByRecursion( arr));
    //                                    ^^^^ This does NOT pass an array
}

---

Eljay's 展示了如何正确实现 OP 的算法。

纯属娱乐⁽¹⁾，堆栈友好的实现

#include <iostream>

int sumByRecursion(size_t n, int const* arr)
{
    // Stop the bloody recursion
    if ( n == 0 )
        return 0;
    if ( n == 1 )
        return arr[0];
    
    // Divide et impera
    size_t middle = n / 2;
    return sumByRecursion(middle, arr)
         + sumByRecursion(n - middle, arr + middle);
}

int main()
{
    int arr[] {2, 4, 6};

    std::cout << sumByRecursion(std::size(arr), arr) << '\n';
}

^{(1) 说真的，不要用这个。这是完全低效和无用的复杂。请改用右边的 algorithm。}

Answer 3

我可以使用算法深度优先搜索.

提供您问题的解决方案

#include <iostream>
#include <vector>
using namespace std;
const int maximumSize=10;
vector<int> visited(maximumSize, 0);
int dfs(int current, int previous, vector<int>& input)
{
    if(visited[current]==1)
    {
        return 0;
    }
    visited[current]=1;
    int summarize=0;
    for(int next=(current+1); next<input.size(); ++next)
    {
        if(next==previous)
        {
            continue;
        }
        summarize+=dfs(next, current, input);
    }
    summarize+=input[current];
    return summarize;
}
void solve()
{
    vector<int> inputVector={2, 4, 6};
    cout<<dfs(0, -1, inputVector);
    return;
}
int main()
{
    solve();
    return 0;
}

结果如下：

12