Sum of First N Numbers: Your First Real Recursion

Adding up 1 + 2 + 3 + ... + n is arithmetic you could do in kindergarten. Writing it recursively is where a lot of people first meet the call stack — and where recursion stops being a scary word and becomes a tool.

The whole trick is one sentence: the sum up to n is just n plus the sum up to n - 1. Say that out loud and you've already written the function. Everything else is learning to trust that a function can call itself and the machine will keep the bookkeeping straight.

Master this and factorial, power-of-two, and every "reduce the problem by one" recursion clicks into place with the same shape.

The problem#

Given a non-negative integer n, return the sum of every integer from 1 up to and including n.

The constraint that makes this a recursion exercise (rather than a for loop): solve it by having the function call itself on a smaller input, not by iterating. That forces you to answer the two questions every recursive solution needs — when do I stop, and how do I shrink the problem?

The brute force baseline#

The loop version is honest and fast, and it's worth writing first so you know what recursion is standing in for:

Nothing is wrong with this — it's O(n) time and O(1) space. But it hides the structure the problem is trying to teach. It walks up from 1 to n with a running accumulator. Recursion instead walks down from n to 0 and lets the language's call stack do the accumulating on the way back up. Same answer, different mental model — and the recursive model is the one that generalizes to trees, backtracking, and divide-and-conquer.

The key insight: define the answer in terms of a smaller answer#

Recursion works when you can express a problem as a slightly smaller copy of itself. For the sum from 1 to n:

sum(5) is 5 + sum(4). sum(4) is 4 + sum(3). Keep peeling one number off the top and the input keeps shrinking. That's the recursive case.

But shrinking forever overflows the stack. You need a floor — a case simple enough to answer with no further recursion. Here it's sum(0) = 0: an empty sum is zero. That's the base case, and it's the anchor the whole chain returns through.

Every well-formed recursion has exactly these two parts:

• A base case that returns a direct answer (n === 0 → 0).
• A recursive case that does a little work and delegates the rest to a smaller call (n + sumFirstN(n - 1)).

The optimal solution#

Here's the exact function the visualizer traces, step for step:

Two lines of logic. Read it as a promise: "if there's nothing left, the sum is 0; otherwise, hand me the sum of everything below n and I'll add n to it."

The order matters. The base-case check comes first. If it didn't, a call with n === 0 would try to compute 0 + sumFirstN(-1), then -1 + sumFirstN(-2), and spiral past your floor forever until the stack overflows. The guard clause at the top is what makes the recursion terminate.

Notice what the function does not have: no loop, no accumulator variable, no explicit stack. The JavaScript call stack is the accumulator. Each pending n + ... waits, frozen mid-expression, until its child call returns a number to slot in.

Walkthrough#

Trace sumFirstN(5). The calls stack up on the way down (each frame paused, waiting on sumFirstN(n - 1)), hit the base case, then resolve on the way up.

Five frames pile onto the stack, deepest first. The moment sumFirstN(0) returns 0, the stack unwinds: each paused frame receives the value from its child, adds its own n, and passes the running total up one level. 0 → 1 → 3 → 6 → 10 → 15. The final 15 is the answer that bubbles all the way back to the top.

That up-and-down motion — build the stack descending, collapse it ascending — is the heartbeat of linear recursion. Watch it animate frame by frame in the Sum of First N Numbers visualizer.

Complexity#

The recursion is O(n) in both time and space — and the space cost is the catch. The iterative loop is O(1) space; recursion pays O(n) because every un-returned frame sits on the stack simultaneously. For large n that stack depth is a real limit (see the mistakes below).

There's also a closed form: n * (n + 1) / 2 gives the answer in O(1) time and space with zero recursion. 5 * 6 / 2 = 15. It's strictly faster — but it teaches you nothing about the call stack, which is the whole point of solving this one recursively.

Common mistakes#

• Forgetting the base case. With no if (n === 0) guard, the function recurses through negative numbers forever and throws RangeError: Maximum call stack size exceeded. The base case is not optional decoration — it's the terminator.
• Putting the base check after the recursive call. The guard must run before sumFirstN(n - 1). Reverse them and you recurse first, overshoot the floor, and overflow.
• Wrong base value. Returning 1 instead of 0 for sumFirstN(0) (confusing it with factorial, where 0! = 1) makes every answer off by one. An empty sum is 0.
• Blowing the stack on huge n. JavaScript engines cap recursion depth around 10⁴–10⁵ frames. For n in the millions, recursion overflows where the loop or the closed form sails through. Recursion here is a teaching tool, not the production choice.
• Assuming tail-call optimization saves you. return n + sumFirstN(n - 1) is not a tail call — the addition happens after the recursive return, so the frame can't be discarded. Most JS engines don't eliminate it anyway.

Where this pattern shows up next#

The "answer in terms of a smaller answer" shape is the entire foundation of recursion. Once sum(n) = n + sum(n - 1) makes sense, these are the same idea wearing different clothes:

• Sum of All Numbers in Array — the same reduction, but shrinking an array index instead of a counter.
• Factorial of N — swap + for * and the base case for 1, and you've got n! = n * (n-1)!.
• Power of Two — recursion that halves instead of decrements, deciding a yes/no on the way down.
• Recursion Masterclass — the full tour: base cases, the call stack, tree recursion, and when to reach for it.

FAQ#

Why use recursion when a loop or a formula is faster?#

Because the goal isn't the sum — it's learning recursion. The closed form n * (n + 1) / 2 beats both in O(1) time, and a loop is O(1) space versus recursion's O(n). You solve this recursively to internalize how a function calls itself, how the call stack stores pending work, and how values return on the unwind. That mental model is what unlocks tree traversal, backtracking, and divide-and-conquer, where recursion genuinely is the clean solution.

What is the base case and why does it matter?#

The base case is the input simple enough to answer without recursing further — here, sumFirstN(0) = 0. It's the floor that stops the descent. Without it, the function calls itself on -1, -2, and so on forever, piling frames onto the stack until the engine throws a stack-overflow error. Every correct recursion needs a base case, and it must be checked before the recursive call runs.

Why is the space complexity O(n) and not O(1)?#

Because all n calls are open at once. When sumFirstN(5) calls sumFirstN(4), the outer frame doesn't finish — it pauses mid-expression, holding onto its 5 + ..., waiting for the child to return. So just before the base case fires, the stack holds five paused frames simultaneously. That stack of un-returned frames is the O(n) space. An iterative loop keeps a single accumulator variable, so it's O(1).

What happens if n is very large?#

The recursion overflows the call stack. JavaScript engines allow only about 10⁴ to 10⁵ nested frames before throwing RangeError: Maximum call stack size exceeded. For n in the hundreds of thousands or millions, recursion crashes where an iterative loop or the closed-form n * (n + 1) / 2 computes the answer instantly. That's the practical trade-off: recursion is the clearest teaching model but the wrong tool when depth gets large.