Recursive vs. Iterative Sum

Problem Statement

Write a Java program that computes the sum of all elements in an array of integers using both recursive and iterative approaches. The program should return the total sum and allow performance comparison between the two methods for large arrays. Test the program with arrays of different sizes, including empty arrays and single-element arrays. You can visualize this as calculating the total cost of items in a shopping list, either by adding items one by one (iterative) or by breaking the list into smaller parts and combining their sums (recursive).

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.
• Input: arr = []
• Output: 0
• Explanation: The sum of an empty array is 0.

Pseudocode

FUNCTION recursiveSum(arr, index)
    IF arr is null OR index equals length of arr THEN
        RETURN 0
    ENDIF
    RETURN arr[index] + recursiveSum(arr, index + 1)
ENDFUNCTION

FUNCTION iterativeSum(arr)
    IF arr is null OR length of arr equals 0 THEN
        RETURN 0
    ENDIF
    SET sum to 0
    FOR each index i from 0 to length of arr - 1
        SET sum to sum + arr[i]
    ENDFOR
    RETURN sum
ENDFUNCTION

FUNCTION mainSum(arr)
    CALL recursiveSum(arr, 0)
    CALL iterativeSum(arr)
    RETURN results
ENDFUNCTION

Algorithm Steps

1. For the recursive approach: a. Check if the array is null or the current index equals the array length. If so, return 0. b. Define a recursive helper function that takes the array and the current index as parameters. c. In the recursive function, add the element at the current index to the result of the recursive call for the next index. d. Call the recursive function with the initial index set to 0.
2. For the iterative approach: a. Check if the array is null or empty. If so, return 0. b. Initialize a variable to store the sum. c. Iterate through the array from index 0 to the last index, adding each element to the sum. d. Return the final sum.
3. In the main function, call both the recursive and iterative methods to compute the sum.
4. Return the results for comparison, ideally measuring execution time for large arrays.

Java Implementation

public class RecursiveVsIterativeSum {
    // Computes sum of array elements using recursion
    public long recursiveSum(int[] arr) {
        // Check for null array
        if (arr == null) {
            return 0;
        }
        // Call recursive helper with initial index 0
        return recursiveSumHelper(arr, 0);
    }

    // Helper function for recursive sum
    private long recursiveSumHelper(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] + recursiveSumHelper(arr, index + 1);
    }

    // Computes sum of array elements using iteration
    public long iterativeSum(int[] arr) {
        // Check for null or empty array
        if (arr == null || arr.length == 0) {
            return 0;
        }
        // Initialize sum
        long sum = 0;
        // Iterate through array and add each element
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
        }
        // Return final sum
        return sum;
    }
}

Output

For the input array [1, 2, 3, 4, 5], both methods output:

15

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

For an empty array [], both methods output:

0

Explanation: The sum of an empty array is 0.

For a single-element array [7], both methods output:

7

Explanation: The sum of a single-element array is the element itself.

How It Works

• Recursive Approach:
  • Step 1: The recursiveSum method checks if the array is null. For [1, 2, 3, 4, 5], it calls recursiveSumHelper with index 0.
  • Step 2: In recursiveSumHelper:
    • Index 0: arr[0] = 1, recurse with index 1.
    • Index 1: arr[1] = 2, recurse with index 2.
    • Index 2: arr[2] = 3, recurse with index 3.
    • Index 3: arr[3] = 4, recurse with index 4.
    • Index 4: arr[4] = 5, recurse with index 5.
    • Index 5: Base case, return 0.
    • Unwind: 5 + (4 + (3 + (2 + (1 + 0)))) = 15.
  • Example Trace: For [1, 2, 3, 4, 5], computes 1 + (2 + (3 + (4 + (5 + 0)))) = 15.
• Iterative Approach:
  • Step 1: The iterativeSum method checks if the array is null or empty. For [1, 2, 3, 4, 5], it initializes sum = 0.
  • Step 2: Iterates: adds 1, 2, 3, 4, 5, resulting in sum = 15.
  • Example Trace: For [1, 2, 3, 4, 5], adds 1 + 2 + 3 + 4 + 5 = 15.
• Performance Comparison: For large arrays (e.g., 10^5 elements), the iterative approach is generally faster due to O(1) space complexity, while the recursive approach uses O(n) stack space, potentially causing stack overflow for very large arrays.

Complexity Analysis Table

Note:

• n is the size of the input array.
• Time complexity: O(n) for both approaches, as each element is processed exactly once.
• Space complexity: O(n) for recursive due to the call stack; O(1) for iterative, using only a single sum variable.
• Best, average, and worst cases are O(n) for both, as all elements are summed.

✅ Tip: Use the iterative approach for large arrays to avoid stack overflow and reduce memory usage. Test both methods with large arrays (e.g., 10^4, 10^5 elements) to compare execution times and verify identical results.

⚠ Warning: The recursive approach may cause stack overflow for very large arrays due to O(n) space complexity. Ensure inputs are within reasonable bounds (e.g., n ≤ 10^5) to prevent performance issues.