Recursively sum integers in an array

Question

I have a program that I am trying to do for a class that returns the sum of all integers in an array using recursion. Here is my program:

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 

But I get three errors that are all related, I suppose, but I can't figure out why it finds a null type:

 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 

Answer 1

The solution is simpler than it looks, try this (assuming an array with a non-zero length):

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

Name it as follows:

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

Answer 2

The problem is that a[n-1] is int , while sumOfArray expects an int array.

Hint: you can simplify the situation by making sumOfArray take the array and the start (or end) index.

Answer 3

 a[n-1] 

gets the value int in n-1, not an array from 0 to n-1.

try using

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

instead

Answer 4

a is an int array. So a[n-1] is int . You pass int to sumOfArray , which expects an array, not an int .

Answer 5

Try this if you do not want to pass the length of the array:

 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)); } 

You should check if the array is empty or not.

Answer 6

This is one recursive solution with complexity O (N) and only with input parameter A [].
You can handle the zero and empty (0 lengths) case, in particular, as “Return 0” in this solution. You also throw an exception in this case.

---

 /* * 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); } } 

Answer 7

How about this recursive solution? You create a smaller sub-array that contains elements from the second to the end. This recursion continues until the size of the array is 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); } } 

Answer 8

 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; } 

Answer 9

Simplified version:

 //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)); }