我正在嘗試使用recursion對給定陣列中的數字求和，嘗試了此代碼但它不起作用。為什么？

#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“空陣列”，則回傳總和。2-如果大小不為0“陣列不為空”，求和上的第一個元素，然后呼叫函式，將陣列的大小減少1，在新陣列上使用sumByRecursion。

uj5u.com熱心網友回復：

您需要將陣列的大小傳遞給sumByRecursion例程。

需要傳遞陣列大小的原因是陣列不跟蹤自己的大小。

替代方案喜歡std::array并std::vector提供查詢它們大小的能力，但 C 風格的陣列不攜帶這些資訊。

該std::size函式查詢型別（在該背景關系中是一個 C 風格的陣列）以確定大小。一旦作為int arr[]引數傳遞，該arr型別就int*不再能夠產生大小資訊。

該int arr[]引數是寫作的一種方式int* arr，但建議讀者該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";
}

uj5u.com熱心網友回復：

一個（可悲的）常見錯誤：

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

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

正如評論部分中已經指出的

在函式內部，引數arr已衰減為 int* 型別，并且對陣列中的元素數量一無所知。（理查德·克里頓）

簡而言之：int sumByRecursion( int arr[])與int sumByRecursion( int *arr). 這[]在引數串列語法無非是語法糖。（保羅·麥肯齊）

解決方案是將大小與指標一起傳遞，明確作為單獨的函式引數或在像std::span或 之類的物件內部std::ranges::range。

當然，另一種方法是傳遞由std::cbegin()和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的回答顯示了如何正確實作 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) 說真的，不要使用它。這是完全低效和無用的復雜。改用正確的演算法。}

uj5u.com熱心網友回復：

我可以提供您的問題的解決方案，使用演算法深度優先搜索。

#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

標籤：C 递归 执行

上一篇：遞回求和函式javascript

下一篇：c -如何在C 中的k個節點之后遞回拆分鏈表？