1. Overview
1.概述
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
2.带数组复制的递归
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.
显然，上述数组中的整数之和是 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].
数组中数字求和的通常方法是 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.
现在，如果我们将 sumOf() 作为函数或方法来看，我们可以看到 sumOf() 的主体再次调用了 sumOf() 。因此，sumOf() 是一个递归方法。
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.
由于 Java 不允许我们在创建数组后更改数组的长度，因此 从数组中删除元素在技术上是不可能的。但是 Java 提供了各种方法来复制数组。我们可以使用这些方法创建子数组。
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.
当我们实现递归方法时，定义基例至关重要。基例是退出递归的某个点。否则，如果没有基例，方法将无休止地递归调用自身，直到 StackOverflowError 被抛出。
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.
正如我们在 sumIntArray1() 方法中看到的，我们使用 Arrays.copyOfRange() 方法来创建子数组。
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))))
= 15Next, let’s test the method with INT_ARRAY:
接下来，让我们用 INT_ARRAY 测试一下该方法：
assertEquals(15, sumIntArray1(INT_ARRAY));3. Recursion Without Creating Array Copies
3.不创建数组副本的递归
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.
在 sumIntArray1() 方法中，我们使用了 Arrays.copyOfRange() 方法来初始化子数组。但是，每次调用该方法都会创建一个新数组。如果我们面对的是一个巨大的整数数组，这种方法会创建许多数组对象。
We know we should avoid creating unnecessary objects to gain better performance. So, next, let’s see if we can improve the sumIntArray1() method.
我们知道，为了获得更好的性能，我们应该避免创建不必要的对象。因此，接下来让我们看看能否改进 sumIntArray1() 方法。
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:
如果我们使用 INT_ARRAY 输入进行测试，则测试通过：
assertEquals(15, sumIntArray2(INT_ARRAY, INT_ARRAY.length - 1))Next, let’s understand how the sumIntArray2() method works.
接下来，让我们了解一下 sumIntArray2() 方法的工作原理。
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:
该方法需要两个参数：整数数组（array）和我们打算计算总和的最后一个索引（lastIdx）。这次，递归遵循这一规则：
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:
正如我们所见，我们在每个递归步骤中都重复使用了原始数组。这种方法的基本情况是当 lastIdx 为零时，这意味着我们已经反向（从 n ->0）走过了整个数组：
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().
最后，让我们进行一次性能比较，看看在输入相同的情况下，sumIntArray2() 是否比 sumIntArray1() 更快。
4. Benchmarking the Two Recursive Solutions
4.两种递归解决方案的基准测试
We’ll use JMH (Java Microbenchmark Harness) to benchmark the two recursive solutions. So, let’s first create a benchmark class:
我们将使用 JMH（Java Microbenchmark Harness）对两个递归解决方案进行基准测试。因此，让我们首先创建一个基准类：
@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:
我们的目的是对这两种解决方案进行基准测试。因此，为了简洁起见，我们将不讨论每个 JMH 配置或注解。但是，我们必须了解，SumArrayBenchmark 使用两个不同的输入数组来执行每个解决方案： </em
- 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.
此外，JMH 还对每个输入阵列的每个解决方案进行五次迭代，确保对其性能进行全面评估。
Next, let’s look at the output SumArrayBenchmark produced:
接下来，让我们看看 SumArrayBenchmark 的输出结果：
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:
正如报告所示，withoutArrayCopy() 解决方案要比 withArrayCopy() 方法快得多：
- Array[10] ~ 5 times faster (30576/6764)
- Array[10000] ~ 242 times faster (7314150/30140)
5. Conclusion
5.结论
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.
在本文中，我们探讨了递归求和数组中整数的两种方法。此外，我们还使用 JMH 工具分析了它们的性能。无数组拷贝 “方案比 “有数组拷贝 “方案快得多。
As always, the complete source code for the examples is available over on GitHub.
与往常一样，这些示例的完整源代码可在 GitHub 上获取。