递归地对数组中的整数求和

Question

我正在尝试为课程制作一个程序，使用递归返回数组中所有整数的总和。以下是我的程序：

public class SumOfArray {

private int[] a;
private int n;
private int result;

    public int sumOfArray(int[] a) {

      this.a = a;
      n = a.length;

      if (n == 0)  // base case
      result = 0;
      else
          result = a[n] + sumOfArray(a[n-1]);

      return result;

   } // End SumOfArray method

} // End SumOfArray Class 

但是我遇到了三个错误，它们都是相关的，我相信，但是我无法弄清楚为什么它会找到一种空类型：

SumOfArray.java:25: sumOfArray(int[]) in SumOfArray cannot be applied to (int)
    result = a[n] + sumOfArray(a[n-1]);
                    ^
SumOfArray.java:25: operator + cannot be applied to int,sumOfArray
    result = a[n] + sumOfArray(a[n-1]);
              ^
SumOfArray.java:25: incompatible types
found   : <nulltype>
required: int
    result = a[n] + sumOfArray(a[n-1]);
                  ^
3 errors

- Maggie S.

---

使用递归在这种情况下不仅更加复杂，而且速度要慢得多。我认为这只是一个练习。 - Peter Lawrey

Answer 1

解决方案比看起来的要简单，尝试以下做法（假设数组长度非零）：

public int sumOfArray(int[] a, int n) {
    if (n == 0)
        return a[n];
    else
        return a[n] + sumOfArray(a, n-1);
}

这样调用：

int[] a = { 1, 2, 3, 4, 5 };
int sum = sumOfArray(a, a.length-1);

- Óscar López

---

在课堂上仅仅提供答案并不是一个好的做法。学生不会从中学到东西。你需要解释其中的错误之处。 - StilesCrisis

Answer 2

问题在于a[n-1]是一个int，而sumOfArray需要一个int数组。

提示：您可以通过使sumOfArray接受数组和起始（或结束）索引来简化事情。

- NPE

Answer 3

a[n-1] 

获取的是n-1处的整数，而不是从0到n-1的数组。
尝试使用：

Arrays.copyOf(a, a.length-1);

取而代之

- Cruncher

---

我相信你也可以使用 Arrays#CopyOfRange。 - Paul Richter

真的吗？这个（可怕的）方法能够运行并不意味着它是正确的方法。 - Luiggi Mendoza

@LuiggiMendoza Arrays.copyOf(a, a.length-1); 执行了 OP 希望 a[n-1] 执行的操作。 - Cruncher

是的，我知道，但为什么要创建整个数组的副本并浪费内存和线性处理时间（这将使此算法在内存和时间上均为O(n^2)），而您只需传递一个带有下一个数组元素的整数值以供使用即可，使此算法保持O(n)（在内存和时间上）？正如我在我的最后一条评论中所说：它可以工作（编译、运行并获得预期结果）并不意味着它是正确的方法。 - Luiggi Mendoza

Answer 4

这个递归解法怎么样？你可以制作一个包含第二个元素到最后一个元素的较小子数组。这种递归会持续到数组大小变为1。

import java.util.Arrays;

public class Sum {
    public static void main(String[] args){
        int[] arr = {1,2,3,4,5};
        System.out.println(sum(arr)); // 15
    }

    public static int sum(int[] array){
        if(array.length == 1){
            return array[0];
        }

        int[] subArr = Arrays.copyOfRange(array, 1, array.length);
        return array[0] + sum(subArr);
    }
}

- takasoft

---

这个解决方案使用了更多的内存，但它帮助我理解了一个核心递归概念，所以谢谢。 - mach3

Answer 5

这是一种时间复杂度为O(N)的递归解决方案，只需要输入参数A[]。
你可以特别处理空值和长度为0的情况，在该解决方案中返回0。在这种情况下，你也可以抛出异常。

---

/*
 * Complexity is O(N)
 */
public int recursiveSum2(int A[])
{
    if(A == null || A.length==0)
    {
        return 0;
    }
    else
    {
        return recursiveSum2Internal(A,A.length-1);
    }
}
private int recursiveSum2Internal(int A[],int length)
{
    if(length ==0 )
    {
        return A[length];
    }
    else
    {
        return A[length]+recursiveSum2Internal(A, length-1);
    }
}

- Nick13

Answer 6

没有任何预定义函数。

公共静态整数和（int input []）{

 int n = input.length;

  if (n == 0)  // base case
  return 0;
  
    int small[]=new int[n-1];
    
    for(int i=1;i<n;i++)
    {
        small[i-1]=input[i];
    }

      return input[0]+sum(small);
    
}

- Krunal

---

请在格式化的代码中添加方法签名。 - Satheesh

Answer 7

如果您不想传递数组的长度，请尝试使用以下方法：

private static int sumOfArray(int[] array) {

        if (1 == array.length) {
            return array[array.length - 1];
        }

        return array[0] + sumOfArray(Arrays.copyOfRange(array, 1, array.length));
    }

当然需要检查数组是否为空。

- samach

Answer 8

a 是一个 int 数组。因此，a[n-1] 是一个 int。您正在向期望数组而不是 int 的 sumOfArray 传递一个 int。

- Steve Kuo

Answer 9

private static int sum(int[] arr) {
    // TODO Auto-generated method stub
    int n = arr.length;

    if(n==1)
    {
        return arr[n-1];
    }

    int ans = arr[0]+sum(Arrays.copyOf(arr, n-1));

    return ans;
}

- Amandeep Singh

Answer 10

简化版：

//acc -> result accumlator, len - current length of array

public static int sum(int[] arr, int len, int acc) {
    return len == 0 ? acc :  sum(arr, len-1,  arr[len-1]+ acc); 
}   
public static void main(String[] args)  {
    int[] arr= { 5, 1, 6, 2};
    System.out.println(sum(arr, arr.length, 0));
}

- Naresh Krishnamoorthy