如何递归地对C中二维数组的元素求和

Question

我尝试了很多方法，如果我可以使用迭代而不是递归会容易得多，但这是作业。

到目前为止，我已经有了将总和分开的想法。一个函数递归地计算列的总和，并调用该函数，以便我可以将所有总和添加到另一个函数中以获得总数。谁能帮助我编写代码，或者如果您有 better/simpler 想法，请分享。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

float sum_colum(float b[], int m){

    float result;

    if (m == 0)
        result = 0;
    else
        result = sum_colum(b, m-1) + b[m-1];

    return result;
}

float sum_total(float a[][100], int n, int m){

    float f = 0;
    int i = 1;

    float col = sum_colum(b, );
    while(i <= n){
        f += col[i];
        n--;
    }
    return f;
}
void main(){

    float x[100][100];
    int i, j, n, m;

    printf("Number of rows: "); scanf("%d", &n);
    printf("Number of colums: "); scanf("%d", &m);

    for(i=0; i<n; i++){
        for(j=0; j<m; j++){
            printf("x[%d][%d] = ", i, j);
            scanf("%f", &x[i][j]);
        }
    }

    printf("The sum of elemets of a 2D array is: %.2f", sum_total(x, n, m));
}

Answer 1

求解 1D 数组的递归解法。递归从末尾开始（行的最后一个索引），在遇到 0 索引处的第一个元素时停止。在二维矩阵中，每一行都是一个 1D 数组。

float sum_row (float row[], int ci) {
    return (0 == ci) ? row[ci] : row[ci] + sum_row (row, ci - 1) ;
}

现在将该逻辑扩展到矩阵中的每一行。我们再次从最后一行递归并在到达 row-index 0.

float sum_matrix (float mat[][MAX_COLS], int ri, int cols) {
    if (0 == ri)
        return sum_row (mat[0], cols);
    else
        return sum_row (mat[ri], cols) + sum_matrix (mat, ri -1, cols);
}

现在测试它，因为 C array-indexes 从 0 开始，我们将 MAX_ROWS-1 & MAX_COLS-1 作为最高值 row-index & column-index可以分别拿。

当您从用户那里读取 rows 和 columns 值时，您将使用：

float sum = sum_matrix (mat, rows - 1, columns - 1);

#include <stdio.h>

#define MAX_ROWS    10
#define MAX_COLS    10

int main() {
    float mat[MAX_ROWS][MAX_COLS];

    for (int ri = 0; ri < MAX_ROWS; ++ri) {
        for (int ci = 0; ci < MAX_COLS; ++ci) {
            mat[ri][ci] = (float) ri * ci;
            printf ("%12.6f ", mat[ri][ci]);
        }
        putchar('\n');
    }
    float sum = sum_matrix(mat, MAX_ROWS-1, MAX_COLS-1);
    printf ("2D Matrix Sum with Recursion: %f\n", sum);
}

注：

当迭代解决方案在资源上更便宜（时间 + space）时，不建议使用递归。
如果矩阵浮点值太大 (+/-)，sum 可能 overflow/underflow。您可能想为 sum 使用 double 存储；两个函数都应 return 一个 double 值。截至目前，在主流系统中，double（使用 8 个字节）可以存储更大范围的值，而不是 float（4 个字节）。

Answer 2

对于任何问题，递归几乎总是错误的解决方案：它缓慢、危险、消耗内存并且通常不必要地难以阅读或实现。

话虽这么说，但有一种相当简单的方法可以做到这一点，那就是将二维数组“分解”为一维数组。所有项目都保证相邻分配。（有一些语言律师方面涉及越界处理内部数组，但我将忽略它们，因为递归从一开始就是不好的做法。）

float sum (size_t size, float arr[size])
{
    return size==0 ? 0.0f : 
                     arr[size-1] + sum(size-1, arr);
}

你可以这样称呼它：

int main (void)
{
    float x[3][3] = 
    {
        {1.0f, 2.0f, 3.0f},
        {4.0f, 5.0f, 6.0f},
        {7.0f, 8.0f, 9.0f},
    };

    printf("sum: %f\n", sum(9, (float*)x));
}

生成的机器代码是一些 horrible parallization goo，其中一些编译器无法 tail-call optimize/inline 即使在同一翻译单元中使用 main() 也是如此。这与我的版本相比，在行和列中分解数组要有效得多。这里的主要问题之一是递归无法预测它何时结束，因为它显然无法告诉 compile-time 处的大小（gcc 在这里似乎比 clang 做得更好，但机器代码是很难读）。

现在将 完全废话 与普通循环进行比较：

float sum=0;
float* ptr = (float*)x;
for(size_t i=0; i<9; i++)
  sum+=ptr[i];

导致这个优化得很好的 asm:

.LCPI0_0:
        .quad   0x4046800000000000              # double 45
main:                                   # @main
        push    rax
        movsd   xmm0, qword ptr [rip + .LCPI0_0] # xmm0 = mem[0],zero
        mov     edi, offset .L.str
        mov     al, 1
        call    printf
        xor     eax, eax
        pop     rcx
        ret
.L.str:
        .asciz  "sum: %f\n"

由此我们可以得出结论，使用递归不仅是个坏主意，而且是彻头彻尾的疯狂。我会问你的老师为什么他们教你如何编写糟糕的程序而不是专注于如何编写好的程序。

如何递归地对C中二维数组的元素求和

How to sum the elements of a 2D array in C recursively

c

recursion

matrix