1. Overview
When we work with numbers, summing all integers in an array is a common operation. Also, recursion often lends itself to elegant solutions.
In this tutorial, we’ll explore how to sum integers in an array using recursion.
2. Recursion With Array Copying
First, let’s initialize an array of integers:
private static final int[] INT_ARRAY = { 1, 2, 3, 4, 5 };
Obviously, the sum of the integers in the array above is 15.
A usual approach to sum numbers in an array is sum (array[0-n]) = array[0] + array[1] + array[2] + array[3] + … + array[n].
This method is straightforward. Alternatively, we can look at this problem from a different perspective: the sum of numbers in an array equals the first number plus the sum of a subarray consists of the rest numbers:
sumOf(array[0..n]) = array[0] + sumOf(subArray[1..n]).
Now, if we look at sumOf()Â as a function or method, we can see the sumOf()’s body calls sumOf() again. Therefore, sumOf() is a recursive method.
As Java doesn’t allow us to change the array’s length after the creation, removing an element from an array is technically impossible. But Java has offered various ways to copy an array. We can use these methods to create the subarray.
When we implement recursive methods, defining the base case is crucial. A base case is some point to exit the recursion. Otherwise, without a base case, the method endlessly calls itself recursively until StackOverflowError is thrown.
In our case, the base case is when the subarray has only one element. This is because the subarray is empty after taking out the only number.
So next, let’s implement the recursive method:
int sumIntArray1(int[] array) {
if (array.length == 1) {
return array[0];
} else {
return array[0] + sumIntArray1(Arrays.copyOfRange(array, 1, array.length));
}
}
As we can see in the sumIntArray1() method, we use the Arrays.copyOfRange() method to create the subarray.
If we pass our example input to the method, the recursion steps look like the following:
sumIntarray1(array) = array[0] + sumOfArray1(arr1{2, 3, 4, 5})
= 1 + (arr1[0] + sumIntarray1(arr2{3, 4, 5}))
= 1 + (2 + (arr2[0] + sumIntarray1(arr3{4, 5})))
= 1 + (2 + (3 + (arr3[0] + sumIntarray1(arr4{5})))) <-- (arr4.length == 1) Base case reached
= 1 + (2 + (3 + (4 + (5))))
= 15
Next, let’s test the method with INT_ARRAY:
assertEquals(15, sumIntArray1(INT_ARRAY));
3. Recursion Without Creating Array Copies
In the sumIntArray1() method, we used the Arrays.copyOfRange() method to initialize the subarray. However, a new array will be created every time we call this method. If we face an enormous integer array, this approach creates many array objects.
We know we should avoid creating unnecessary objects to gain better performance. So, next, let’s see if we can improve the sumIntArray1() method.
The idea is to pass the required index to the next recursion step. Then, we can reuse the same array object:
int sumIntArray2(int[] array, int lastIdx) {
if (lastIdx == 0) {
return array[lastIdx];
} else {
return array[lastIdx] + sumIntArray2(array, lastIdx - 1);
}
}
If we test it with our INT_ARRAY input, the test passes:
assertEquals(15, sumIntArray2(INT_ARRAY, INT_ARRAY.length - 1))
Next, let’s understand how the sumIntArray2() method works.
The method takes two parameters: the integer array (array) and the last index up to which we intend to calculate the sum (lastIdx). This time, the recursion follows this rule:
sumOf(array[0..n], n) = array[n] + sumOf(array[0..n], n-1).
As we can see, we reuse the original array in each recursion step. The base case of this approach is when lastIdx is zero, which means we’ve reversely (from n ->0) walked through the entire array:
sumIntArray2(array, 4) = array[4] + sumOfArray2(array, 3)
= 5 + (array[3] + sumIntArray2(array, 2))
= 5 + (4 + (array[2] + sumIntArray2(array, 1)))
= 5 + (4 + (3 + (array[1] + sumIntArray2(array, 0))))
= 5 + (4 + (3 + (2 + (array[0])))) <-- (idx == 0) Base case reached
= 5 + (4 + (3 + (2 + (1))))
= 15
Finally, let’s apply a performance comparison to see, given the same input, whether sumIntArray2() is faster than sumIntArray1().
4. Benchmarking the Two Recursive Solutions
We’ll use JMH (Java Microbenchmark Harness) to benchmark the two recursive solutions. So, let’s first create a benchmark class:
@BenchmarkMode(Mode.AverageTime)
@State(Scope.Thread)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 2)
@Fork(1)
@Measurement(iterations = 5)
public class SumArrayBenchmark {
public static void main(String[] args) throws Exception {
Options options = new OptionsBuilder()
.include(SumArrayBenchmark.class.getSimpleName())
.build();
new Runner(options).run();
}
@Param({ "10", "10000" })
public int size;
int[] array;
@Setup
public void setup() {
var r = new Random();
array = new int[size];
for (int i = 0; i < size; i++) {
array[i] = r.nextInt();
}
}
@Benchmark
public int withArrayCopy() {
return sumIntArray1(array);
}
@Benchmark
public int withoutArrayCopy() {
return sumIntArray2(array, array.length - 1);
}
}
Our objective is to benchmark the two solutions. So, we won’t discuss each JMH configuration or annotation for brevity. However, it’s crucial to understand that SumArrayBenchmark performs each solution with two distinct input arrays:
- An array with 10 random numbers
- An array consists of 10000 random integers
Additionally, JMH conducts five iterations for each input array on each solution, ensuring a thorough evaluation of their performance.
Next, let’s look at the output SumArrayBenchmark produced:
Benchmark (size) Mode Cnt Score Error Units
SumArrayBenchmark.withArrayCopy 10 avgt 5 30,576 ± 0,584 ns/op
SumArrayBenchmark.withArrayCopy 10000 avgt 5 7314150,000 ± 82516,421 ns/op
SumArrayBenchmark.withoutArrayCopy 10 avgt 5 6,764 ± 0,032 ns/op
SumArrayBenchmark.withoutArrayCopy 10000 avgt 5 30140,685 ± 91,804 ns/op
As the report shows, the withoutArrayCopy() solution is much faster than the withArrayCopy() approach:
- Array[10] ~ 5 times faster (30576/6764)
- Array[10000] ~ 242 times faster (7314150/30140)
5. Conclusion
In this article, we’ve explored two approaches to recursively summing integers in an array. Also, we analyzed their performance using the JMH tool. The “withoutArrayCopy” solution is much faster than the “withArrayCopy” approach.
As always, the complete source code for the examples is available over on GitHub.
