c - C中数组的递归和

Question

您好，我正在学习 C 中的递归，我正在尝试找到元素的总和。

这是我的主要内容：

int main()
{


    int arr[] = {1,2,3,4,5};
    int sum;
    sum = arr_sum(arr,4);
    printf("\nsum is:%d",sum);



    return 0;

}

我的递归函数：

//n is the last index of the array

int arr_sum( int arr[], int n )
{ // must be recursive

    int sum = 0;
    //base case:
    if (n < 0) {
        return sum;
    } else{
        sum = sum + arr[n];
    }
    //make problem smaller
    arr_sum(arr,n-1);
}

输出是：

sum is :0 

Answer 1

试试这个你的递归函数：

int arr_sum( int arr[], int n ) { 
  if (n < 0) {
    //base case:
    return 0;
  } else{
    return arr[n] + arr_sum(arr, n-1);
  }
}

您需要将第 n 个案例添加到您的 n-1 个案例中，直到您到达基本案例。

Answer 2

您可以添加第三个参数，即到目前为止计算的运行总计（以 开头0）。

当您递归调用该函数时，传递运行总计。

int arr_sum( int arr[], int n, int sum )
{ // must be recursive

    if (n < 0) {
         return sum;
    }

    sum += arr[n];

    return arr_sum(arr, --n, sum);
}

或者，您将其更改为不需要sum像这样传递变量。

int arr_sum( int arr[], int n )
{ // must be recursive

    if (n < 0) {
         return sum;
    }

    return arr[n] + arr_sum(arr, n - 1);
}

这样，它类似于在斐波那契数列中找到一个数字。

Answer 3

试试你的程序的这个修改版本，并在笔/纸上计算它的流动方式。希望能帮助到你。

#include <stdio.h>

//n is the last index of the array
int
arr_sum(int arr[], int n )
{
    //base case:
    if (n == 0) {
        return arr[0];
    }

    return (arr[n] + arr_sum(arr,n-1));
}

int
main(void)
{
    int arr[] = {1,2,3,4,5};
    int sum;

    sum = arr_sum(arr,4);
    printf("\nsum is:%d\n",sum);

    return 0;
}

Answer 4

你没有从其他部分返回任何东西。你也有回报。像。

return arr_sum(arr,n-1)+arr[n];

所以这会一次又一次地调用该函数，直到 n 为零。

你明白我的意思了吗？

Answer 5

您的代码的问题在于，每次调用递归函数时，都会将总和初始化为0.

sum在将解决问题的递归方法之外声明。