Recursive Sum of Array

Problem Statement

Write a Java program that uses recursion to compute the sum of all elements in an array of integers. The program should take an array as input and return the total sum of its elements. Test the program with arrays of different sizes, including empty arrays and single-element arrays. You can visualize this as calculating the total score of a student’s test results stored in a list, where you add each score one by one recursively.

Input: An array of integers (e.g., arr = [1, 2, 3, 4, 5]). Output: An integer representing the sum of all elements in the array (e.g., 15 for [1, 2, 3, 4, 5]). Constraints:

• The array length is between 0 and 10^5.
• Elements are integers between -10^9 and 10^9.
• The array may be empty. Example:
• Input: arr = [1, 2, 3, 4, 5]
• Output: 15
• Explanation: The sum is calculated as 1 + 2 + 3 + 4 + 5 = 15.

Pseudocode

1. If the array is null or empty, return 0.
2. Define a recursive function sumArray(arr, index):
   a. Base case: If index equals array length, return 0.
   b. Recursive case: Return arr[index] + sumArray(arr, index + 1).
3. Call sumArray(arr, 0) to start recursion from the first element.
4. Return the result.

Algorithm Steps

1. Check if the input array is null or empty. If so, return 0, as the sum of no elements is zero.
2. Define a recursive helper function that takes the array and the current index as parameters.
3. In the recursive function, implement the base case: if the index equals the array length, return 0, as no more elements remain to sum.
4. For the recursive case, add the element at the current index to the result of the recursive call for the next index.
5. Initiate the recursion by calling the helper function with the initial index set to 0.
6. Return the final sum computed by the recursive function.

Java Implementation

public class RecursiveArraySum {
    // Computes the sum of array elements using recursion
    public int sumArray(int[] arr) {
        // Check for null or empty array
        if (arr == null || arr.length == 0) {
            return 0;
        }
        // Call recursive helper function starting at index 0
        return sumArrayHelper(arr, 0);
    }

    // Helper function for recursive sum
    private int sumArrayHelper(int[] arr, int index) {
        // Base case: if index reaches array length, return 0
        if (index == arr.length) {
            return 0;
        }
        // Recursive case: add current element to sum of remaining elements
        return arr[index] + sumArrayHelper(arr, index + 1);
    }
}

Output

For the input array [1, 2, 3, 4, 5], the program outputs:

15

Explanation: The sum is computed as 1 + 2 + 3 + 4 + 5 = 15.

For an empty array [], the program outputs:

0

Explanation: The sum of an empty array is 0.

How It Works

• Step 1: The sumArray method checks if the input array is null or empty. For [1, 2, 3, 4, 5], it is valid, so it calls the helper function with index 0.
• Step 2: The sumArrayHelper method implements recursion:
  • At index 0: arr[0] = 1, recursive call for index 1.
  • At index 1: arr[1] = 2, recursive call for index 2.
  • At index 2: arr[2] = 3, recursive call for index 3.
  • At index 3: arr[3] = 4, recursive call for index 4.
  • At index 4: arr[4] = 5, recursive call for index 5.
  • At index 5: Base case reached (index equals length), return 0.
• Step 3: The recursion unwinds: 5 + (4 + (3 + (2 + (1 + 0)))) = 15.
• Example Trace: For [1, 2, 3, 4, 5], the algorithm recursively adds: 1 + sum([2, 3, 4, 5]) = 1 + (2 + sum([3, 4, 5])) = 1 + 2 + (3 + sum([4, 5])) = 1 + 2 + 3 + (4 + sum([5])) = 1 + 2 + 3 + 4 + (5 + sum([])) = 1 + 2 + 3 + 4 + 5 + 0 = 15.

Complexity Analysis Table

Note:

• n is the size of the input array.
• Time complexity: O(n), as the algorithm makes one recursive call per element.
• Space complexity: O(n) due to the recursive call stack, which grows linearly with the array size.
• Best, average, and worst cases are all O(n), as every element is processed exactly once.

✅ Tip: Use recursion for problems like array summation when the logic is naturally recursive, and test with edge cases like empty arrays or single-element arrays to ensure correctness.

⚠ Warning: Be cautious with large arrays, as the O(n) space complexity from the recursive call stack can lead to stack overflow errors. Consider iterative solutions for very large inputs.