Calculate the Sum from 1 to N with Recursion

The sum through 4 is 4 plus the sum through 3

To calculate the sum from 1 to n, separate the current number from all smaller numbers. The current call contributes n, and the smaller recursive call calculates the sum from 1 to n - 1. That gives the recursive case sum(n) = n + sum(n - 1). For n = 4, the expression is sum(4) = 4 + sum(3).

The call sum(3) does not already contain 4. It asks for 3 + 2 + 1, which is the smaller part of the answer. The current call still has to contribute 4, so returning only sum(3) would calculate 6, not 10. Each call contributes its own n exactly once.

sum(4) = 4 + sum(3)
sum(3) = 3 + sum(2)
sum(2) = 2 + sum(1)
sum(1) = 1 + sum(0)

Returning 0 at sum(0) stops the calls without changing the total

The recursive case keeps reducing n by 1, so the computation needs a reachable stopping point. Define sum(0) = 0. This value adds nothing to the total, while the call itself ends the descent. The rule is valid under the precondition n >= 0, because every recursive call then moves toward 0.

For the running computation, sum(1) asks for sum(0), and sum(0) immediately returns 0. If you omit this reachable base case, the same recursive rule continues from sum(0) to sum(-1), then sum(-2), and so on. It does not produce 10, because the calls never get a value that lets them return. In a real program, the call stack eventually overflows.

The answer becomes 10 only while the calls return

The calls first descend from sum(4) to sum(0). At that point, sum(0) returns 0. The pending additions then complete in reverse order: sum(1) returns 1 + 0 = 1, sum(2) returns 2 + 1 = 3, sum(3) returns 3 + 3 = 6, and sum(4) returns 4 + 6 = 10.

Descending creates the pending work, but descending does not calculate the final answer by itself. Each call is paused while its recursive call runs. The return value from the smaller call fills that paused call's expression, allowing the current value to be added. The call stack therefore holds four pending additions above the base case.

sum(0) returns 0
sum(1) returns 1 + 0 = 1
sum(2) returns 2 + 1 = 3
sum(3) returns 3 + 3 = 6
sum(4) returns 4 + 6 = 10

One shrinking call per level makes both costs linear

Let T(n) be the time used by sum(n). One call performs constant work to add n and makes one call on n - 1, so the recurrence is T(n) = T(n - 1) + Theta(1), with T(0) = Theta(1). Each step reduces n by one, giving O(n) time for sum(n). For sum(4), the active calls are sum(4), sum(3), sum(2), sum(1), and sum(0), five frames in total.

Those active frames determine the auxiliary space as well. The calls cannot be removed until their smaller calls return, so the stack grows to n + 1 frames for an input n. The auxiliary stack space is therefore O(n). The returned answer itself is one number, but the pending call frames still occupy memory while the descent is in progress.