C - 数组的递归累加和

Question

我的任务是制作一个递归函数，该函数接受一个数字数组，并将其转换为到目前为止所有数字的累加和数组，因此：

1、2、3、4、5 变成 1、3、6、10、15

这是我想出的：

#include <stdio.h>

int cumul(int tab[], int length, int ind) {

    if (ind > 0) {
        tab[ind] += tab[ind-1];
    }
    if (ind < length) {
        cumul(tab, length, ind+1);
    }
    return 0;
}

int main() {
    int ind;
    int tab[6] = {1, 2, 3, 4, 5, 6};
    int length = sizeof(tab)/sizeof(tab[0]);

    for (ind = 0; ind < length; ind++) {
        printf("%d ", tab[ind]);
    }
    printf("\n");

    cumul(tab, length, 0);

    for (ind = 0; ind < length; ind++) {
    printf("%d ", tab[ind]);
    }
    printf("\n");
    return 0;
}

它在大多数情况下运行良好，但我遇到了奇怪的特定数组的障碍：

例如，它不适用于 tab[6] = {1, 2, 3, 4, 5, 6}，这里是输出：

1 2 3 4 5 6 
1 3 6 10 15 21 27 7 4196016 0 -1076574208 32528 -1609083416 32767 -1609083416 32767 0 1 4195802 0 0 0 -1815242402 30550560 4195424 0 -1609083424

我不知道为什么它会变得疯狂。它适用于我尝试过的几乎所有 tab[5] 和 tab[7] 数组，但对我尝试过的每个 tab[6] 数组都失败。

Answer 1

当 ind 达到 length-1 时出现问题。比如length是6，ind是5，那么递归调用就是

cumul(tab, 6, 6);  // length=6 ind+1=6

在递归的下一级，在 if ( ind > 0 ) 之后，代码将执行此操作

tab[6] += tab[5];  // ind=6 ind-1=5

这会导致未定义的行为，因为您写入的内容超出了数组的末尾。

您可以在第一个 if 语句中检查上限，例如

if ( ind > 0 && ind < length )

但是最好通过将第二个 if 语句更改为

来避免递归调用

if ( ind < length - 1 )

任一更改都避免了您访问 tab[length].

的情况

C - 数组的递归累加和

C - Recursive, cumulative sum of an array

c

arrays

recursion