Write a recursive method that computes $\sum_{i=0}^{n} i$, and compare it with the closed form.

Question

Accepted Answer

Same skeleton as factorial — base case 0, otherwise n + recursiveSum(n-1) — but the closed form $\frac{n(n+1)}{2}$ gets the same answer in $O(1)$.
public static int recursiveSum(int n) {
  if (n == 0) {
    return 0;                        // base case: empty sum is 0
  } else {
    return n + recursiveSum(n - 1);  // n plus the sum of everything below
  }
}

For $n = 100$ both routes give 5050:

Approach
Cost
Memory

recursiveSum(100)
$O(n)$ — one call per value
$O(n)$ — one stack frame per call

100 * 101 / 2
$O(1)$
$O(1)$

Note the base case: for a sum the neutral element is 0, while for a product (factorial) it is 1. Returning the wrong one gives an answer that is wrong by a constant or collapses to zero — a classic off-by-identity bug.
The real lesson: recursion mirrors the definition of the sum, and that is genuinely valuable when no closed form exists. But when one does, it wins outright — $O(1)$ against $O(n)$ time and $O(n)$ stack. Knowing the mathematics of your problem beats implementing its definition faithfully.

Approach	Cost	Memory
`recursiveSum(100)`	$O(n)$ — one call per value	$O(n)$ — one stack frame per call
`100 * 101 / 2`	$O(1)$	$O(1)$