public class ArraySum
1:
2: import java.util.ArrayList;
3: import java.util.List;
4: import java.util.Random;
5:
6: /**
7: * Find the sum of the values in a List. RECURSIVELY.
8: *
9: * NOTE: Recursively is a silly way to do this, but it's an exercise in thinking
10: * recursively.
11: *
12: * @author Mark Young (A00000000)
13: */
14: public class ArraySum {
15:
16: /**
17: * @param args the command line arguments
18: */
19: public static void main(String[] args) {
20: List<Integer> numbers = generateRandomNumbers(10);
21:
22: System.out.println("The sum of the values in " + numbers);
23: System.out.println("is " + getSum(numbers) + ".");
24: }
25:
26: /**
27: * Generate numElts random numbers in the range [0, 1000).
28: *
29: * @param numElts the number of elements in the result
30: * @return a list of random numbers
31: */
32: private static List<Integer> generateRandomNumbers(int numElts) {
33: List<Integer> result = new ArrayList<>();
34: Random rand = new Random();
35:
36: for (int i = 0; i < numElts; ++i) {
37: result.add(rand.nextInt(1000));
38: }
39:
40: return result;
41: }
42:
43: /**
44: * Calculate the sum of an array's elements.
45: *
46: * @param numbers the number whose digits are summed
47: * @return the sum of those digits
48: */
49: private static int getSum(List<Integer> numbers) {
50: return getSum(numbers, 0, numbers.size());
51: }
52:
53: /**
54: * RECURSIVELY calculate sum of part of a List -- starting with index lo
55: * and ending just before index hi. To sum the entire List, lo should be
56: * zero and hi should be the size of the List.
57: *
58: * PRECONDITION: 0 ≤ lo ≤ hi ≤ numbers.size()
59: *
60: * @param numbers the list of numbers
61: * @param lo the lowest index included in the part
62: * @param hi the index just above the highest included in the part
63: * @return the sum of the elements numbers[lo..hi)
64: */
65: private static int getSum(List<Integer> numbers, int lo, int hi) {
66: if (hi == lo) {
67: return 0;
68: } else if (hi - lo == 1) {
69: return numbers.get(lo);
70: } else {
71: int mid = (lo + hi) / 2;
72: return getSum(numbers, lo, mid) + getSum(numbers, mid, hi);
73:
74: /* OR */
75: // return numbers.get(lo) + getSum(numbers, lo + 1, hi);
76:
77: /* OR */
78: // return numbers.get(hi - 1) + getSum(numbers, lo, hi - 1);
79: }
80: }
81:
82: }