c++ - 在 C++ 中递归地总结链表中的元素

Question

假设我有一个 Sum 方法来帮助递归地对链表中的元素求和，

void Sum(Node *head)
{
    int sum = 0;   //I think this is the problem since it resets the sum on each recursive call
    while (head != NULL) {
        Sum(head->next); //iterate to the last node before null
        sum += head->data; 
        return;
    }

    cout << " The sum is : " << sum << endl;
}

我认为我遇到的问题是由于每次递归返回调用时我的总和值被重新初始化为 0；在所有递归完成后，有什么方法可以让我保持总和的值？

Answer 1

它可以比您拥有的简单得多。我建议的更改:

1. 更改函数的返回值，使其返回总和。
2. 在递归调用中使用返回值。
3. 不要使用while 循环和递归调用。使用其中之一。

递归版本:

int Sum(Node *head)
{
    if ( head != NULL )
        return head->data + Sum(head->next);
    else
        return 0;
}

循环版:

int Sum(Node *head)
{
   int sum = 0;
   while (head != NULL) {
     sum += head->data; 
     head = head->next;
   }
   return sum;
}