Tail-Recursive Sum

Problem Statement

Write a Java program that computes the sum of all elements in an array of integers using a tail-recursive function with an accumulator to track the running sum. The program should return the total sum and test the function with arrays of different sizes, including empty arrays and single-element arrays. You can visualize this as tallying the total score of a series of games, where each game’s score is added to a running total, passing the updated total to the next step recursively until all scores are processed.

Input: An array of integers (e.g., arr = [1, 2, 3, 4, 5]). Output: A long 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 tailRecursiveSum(arr, index, accumulator)
    IF arr is null OR index equals length of arr THEN
        RETURN accumulator
    ENDIF
    SET newAccumulator to accumulator + arr[index]
    RETURN tailRecursiveSum(arr, index + 1, newAccumulator)
ENDFUNCTION

FUNCTION mainSum(arr)
    IF arr is null THEN
        RETURN 0
    ENDIF
    RETURN tailRecursiveSum(arr, 0, 0)
ENDFUNCTION

Algorithm Steps

1. Check if the input array is null. If so, return 0.
2. Define a tail-recursive helper function that takes the array, the current index, and an accumulator as parameters.
3. In the helper function, implement the base case: if the index equals the array length, return the accumulator.
4. For the recursive case, add the current element to the accumulator and recursively call the function with the next index and the updated accumulator.
5. In the main function, call the tail-recursive function with the initial index set to 0 and the accumulator set to 0.
6. Return the final sum computed by the tail-recursive function.

Java Implementation

public class TailRecursiveSum {
    // Computes sum of array elements using tail recursion
    public long sum(int[] arr) {
        // Check for null array
        if (arr == null) {
            return 0;
        }
        // Call tail-recursive helper with initial index and accumulator
        return tailRecursiveSum(arr, 0, 0);
    }

    // Helper function for tail-recursive sum
    private long tailRecursiveSum(int[] arr, int index, long accumulator) {
        // Base case: if index reaches array length, return accumulator
        if (index == arr.length) {
            return accumulator;
        }
        // Recursive case: update accumulator and recurse
        return tailRecursiveSum(arr, index + 1, accumulator + arr[index]);
    }
}

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.

For a single-element array [7], the program outputs:

7

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

How It Works

• Step 1: The sum method checks if the array is null. For [1, 2, 3, 4, 5], it calls tailRecursiveSum with index = 0 and accumulator = 0.
• Step 2: In tailRecursiveSum:
  • Index 0: accumulator = 0 + 1 = 1, recurse with index = 1, accumulator = 1.
  • Index 1: accumulator = 1 + 2 = 3, recurse with index = 2, accumulator = 3.
  • Index 2: accumulator = 3 + 3 = 6, recurse with index = 3, accumulator = 6.
  • Index 3: accumulator = 6 + 4 = 10, recurse with index = 4, accumulator = 10.
  • Index 4: accumulator = 10 + 5 = 15, recurse with index = 5, accumulator = 15.
  • Index 5: Base case, return accumulator = 15.
• Example Trace: For [1, 2, 3, 4, 5], the accumulator builds: 0 → 1 → 3 → 6 → 10 → 15, returning 15.
• Tail Recursion Note: The function is tail-recursive because the recursive call is the last operation, allowing potential optimization in languages that support tail-call optimization (though Java does not natively optimize tail recursion).

Complexity Analysis Table

Note:

• n is the size of the input array.
• Time complexity: O(n), as the function processes each element exactly once.
• Space complexity: O(n) due to the recursive call stack, as Java does not optimize tail recursion.
• Best, average, and worst cases are O(n), as all elements are processed.

✅ Tip: Use tail recursion with an accumulator to make recursive functions more intuitive by tracking state explicitly. Test with large arrays (e.g., 10^4 elements) and edge cases like empty or single-element arrays to ensure correctness.

⚠ Warning: Java does not optimize tail recursion, so the O(n) space complexity may lead to stack overflow for very large arrays. Consider iterative solutions for better space efficiency in such cases.