c - C 中使用一个参数递归地计算数组的总和

Question

我应该如何在纯 C 中仅使用一个指针递归地计算数组的总和。函数原型(prototype)如下:

int sum(int *arr);

这是我的代码:

int sum(int *arr) {
    int *p, *q;
    p = &arr[0];
    q = p + sizeof(*arr) - 1;
    int total = 0;

    if(p < q) {
        return total + sum(++p);
    }
    else
        return total;
}

Answer 1

不可能

两个问题:

1. 数组在哪里结束？

在 C 语言中，数组只是内存块，没有长度属性。可以从内存的其他部分读取数组末尾的不可预测的数字。

在发布的代码中，sizeof(*arr)显然用于在指针算术中获取数组的长度q = p + sizeof(*arr) - 1

但是sizeof决定数组长度吗？让我们来看看...

#include <stdio.h>
void main(){
  int a[10] = {0,1,2,3,4,5,6,7,8,9};
  int * p = a;
  int l = sizeof(*p);
  printf("%d\n",l);
}

当使用 gcc 编译和运行时，会打印 4，而不是 10。

为什么是4？因为 4 是 int 的大小。

这表明 sizeof 不会提供数组长度。

因此，函数 int sum(int *arr) 将不知道何时停止读取，除非给它一个用于终止的哨兵值或明确的总和长度。在字符串中，最终值为 0，但这里使用 0 的问题是，它是一个完全有效的数字，可以添加到总和中。

需要一个累加器。

大多数递归求和函数本质上是 fold operations因此需要一个累加器来存储部分结果。

现在累加器可能会被放入 static variable 中，但通常不会这样做，因为它不是线程安全的，并且会导致更复杂的代码，涉及复制最终结果和重置累加器。

这建议包含一个累加器参数来保存总和。

如果我们还添加一个长度参数，我们可以这样写:

int sum(int *arr, int len, int accumulator){ 
    if (len==0) return accumulator;
    else return sum(arr+1,len-1,accumulator+*arr);
}

或者，您可以使用函数堆栈来存储累加并剪切累加器参数，如下所示:

int sum(int *arr, int len){ 
    if (len==0) return 0;
    else return sum(arr+1,len-1)+*arr
}

但是单个参数int sum(int *arr)是不可能的，因为它缺少终止求和过程的参数。