1. 概述
当我们处理数字时，数组中所有整数的求和是一个常见的操作。而且，递归常常能提供优雅的解决方案。
在这个教程中，我们将探讨如何使用递归来计算数组中的整数和。
2. 递归与数组复制
首先，我们初始化一个整数数组：
private static final int[] INT_ARRAY = { 1, 2, 3, 4, 5 };
显然，上述数组中的整数之和为15。
在数组中求和的一种常见方法是 sum(array[0-n]) = array[0] + array[1] + array[2] + array[3] + ... + array[n]。
这种方法直接明了。另一种角度来看，数组中的数字和等于第一个数加上剩余数子数组的和：
sumOf(array[0..n]) = array[0] + sumOf(subArray[1..n]).
如果我们把 sumOf() 视为一个函数或方法，我们可以看到 sumOf() 的主体再次调用自身。因此，sumOf() 是一个递归方法。
由于Java不允许在创建后改变数组的长度，从数组中删除元素在技术上是不可能的。但Java提供了多种方式来复制数组。我们可以利用这些方法来创建子数组。
在实现递归方法时，定义基线条件至关重要。基线条件是退出递归的某个点。否则，如果没有基线条件，方法会无限递归调用自己，直到抛出*StackOverflowError*。
在我们的例子中，基线条件是当子数组只有一个元素时。这是因为取出唯一的一个数后，子数组为空。
接下来，让我们实现这个递归方法：
int sumIntArray1(int[] array) {
if (array.length == 1) {
return array[0];
} else {
return array[0] + sumIntArray1(Arrays.copyOfRange(array, 1, array.length));
}
}
如 sumIntArray1() 方法所示，我们使用了Arrays.copyOfRange() 方法来创建子数组。
如果我们用示例输入调用这个方法，递归步骤如下：
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
接下来，让我们用 INT_ARRAY 测试这个方法：
assertEquals(15, sumIntArray1(INT_ARRAY));
3. 不创建数组副本的递归
在 sumIntArray1() 方法中，我们使用了 Arrays.copyOfRange() 方法来初始化子数组。但是，每次调用这个方法时都会创建一个新的数组。如果我们面对一个巨大的整数数组，这种方法会产生很多数组对象。
我们知道应该避免不必要的对象创建以提高性能。那么，让我们看看能否改进 sumIntArray1() 方法。
思路是将所需的索引传递到下一次递归步骤中，这样我们可以重用同一个数组对象：
int sumIntArray2(int[] array, int lastIdx) {
if (lastIdx == 0) {
return array[lastIdx];
} else {
return array[lastIdx] + sumIntArray2(array, lastIdx - 1);
}
}
如果用 INT_ARRAY 输入测试，测试通过：
assertEquals(15, sumIntArray2(INT_ARRAY, INT_ARRAY.length - 1))
接下来，让我们理解 sumIntArray2() 方法的工作原理。
该方法接受两个参数：整数数组（array）和我们打算计算和的最后一个索引（lastIdx）。这次，递归遵循以下规则：
sumOf(array[0..n], n) = array[n] + sumOf(array[0..n], n-1).
如我们所见，每个递归步骤都重用了原始数组。这种方法的基线条件是当lastIdx为0时，这意味着我们已经反向（从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
最后，让我们应用性能比较，看看给定相同的输入，sumIntArray2() 是否比sumIntArray1()更快。
4. 两种递归解法的基准测试
我们将使用JMH（Java微基准测试框架）来基准测试这两种递归解决方案。首先，我们创建一个基准类：
@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);
}
}
我们的目标是基准测试这两个解决方案，因此为了简洁，我们将略过每个JMH配置或注解的讨论。但重要的是要理解，SumArrayBenchmark 对每个解决方案使用两个不同的输入数组：*
- 包含10个随机数的数组
- 由10000个随机整数组成的数组
此外，JMH对每个输入数组的每个解决方案进行五次迭代，确保对其性能有充分的评估。
接下来，我们看看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
报告显示，**withoutArrayCopy解决方案比withArrayCopy方法快得多：**
- 数组[10] ~ 5倍更快（30576/6764）
- 数组[10000] ~ 242倍更快（7314150/30140）
5. 总结
在这篇文章中，我们探讨了两种递归计算数组中整数和的方法，并使用JMH工具分析了它们的性能。withoutArrayCopy解决方案明显比withArrayCopy方法更快。
如往常一样，示例代码的完整源码可以在GitHub上找到。