Java recursion: base cases, stack depth, and bounded work

Prove progress toward the base case

A recursive sum over a half-open array interval stops when the interval is empty. Otherwise it splits the interval and sums its two halves. Both child intervals are smaller than their parent.

The program accumulates as a long even though each stored count is an int. That prevents int-sized intermediate sums from wrapping in this bounded example. It still does not make an arbitrarily enormous long sum overflow-proof.

An invalid split can reproduce the same interval and recurse indefinitely. A correct base case is not enough by itself; every non-base branch must move toward it. Empty input and a single-element interval are useful tests of that progress.

Stack depth is part of space cost

A recursive method call needs stack state. Java does not promise general tail-call elimination, so tail-recursive source should not be described as constant-stack merely because the recursive call appears last.

This balanced sum has logarithmic call depth, but it still visits every element. A linear recursive sum that moves one index each time would use linear depth and could overflow the stack for a large batch.

For a simple sum, an iterative loop is usually easier and uses constant extra space. This recursive form is useful to understand divide-and-conquer structure before studying operations that gain more from the split.

Working program

public class BalancedShipmentSum {
    static long sum(int[] counts, int from, int to) {
        if (from == to) return 0L;
        if (to - from == 1) return counts[from];
        int middle = from + (to - from) / 2;
        return sum(counts, from, middle) + sum(counts, middle, to);
    }
    public static void main(String[] args) {
        int[] dailyCounts = {12, 8, 0, 15, 3};
        System.out.println(sum(dailyCounts, 0, dailyCounts.length));
        System.out.println(sum(new int[0], 0, 0));
    }
}

Output

38
0

Cost and design choices

The recurrence performs two child traversals whose sizes sum to n, plus constant local work. Total work is O(n), not O(log n). Logarithmic split depth does not mean logarithmic total work.

Active recursive frames require O(log n) extra stack space for this balanced implementation. It does not allocate copied subarrays, because both branches reuse the original array with different bounds.

If bounds can come from a caller, validate 0 <= from <= to <= counts.length at a public boundary. The demonstration calls the helper only with valid bounds; its implementation does not hide a separate validation contract.

Connected lessons

Continue with Half-open bounds, Method contracts, Interval narrowing.

Common Mistakes

• Do not forget a base case for an empty interval.
• Do not assume Java eliminates tail-recursive stack frames.
• Do not confuse recursion depth with total work.
• Do not copy a subarray at every split without counting that allocation cost.