Sum of All Numbers in Array: Your First Recursion Problem
Sum every number in an array using recursion — the base case, the recursive step, a call-stack walkthrough, JavaScript code, and complexity, explained clearly.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Adding up an array is the "hello world" of loops — one for, one accumulator, done. So why solve it with recursion? Because this tiny problem is the cleanest place to learn the two moving parts every recursive solution shares: a base case that stops the descent, and a recursive step that shrinks the input by one and trusts itself to handle the rest.
Get the reasoning right here and factorials, tree traversals, and divide-and-conquer stop feeling like magic. They're all the same two parts wearing different clothes.
The problem
Given an array of integers arr, return the sum of all its elements. Nothing fancy — no target, no indices to return, just one number.
Input: arr = [3, 1, 4, 1, 5]
Output: 14 // 3 + 1 + 4 + 1 + 5
Input: arr = [-3, 0, 5, -2, 4]
Output: 4 // negatives and zero are fineThe recursive framing asks one question at a time: "What is arr[i] plus the sum of everything before it?" If you can answer that for the last element, and the answer for a shorter array is handled by the same function, you've solved the whole thing.
The brute force baseline
A loop is the honest baseline, and it's genuinely fine for production code:
function sumArray(arr) {
let total = 0;
for (let i = 0; i < arr.length; i++) {
total += arr[i];
}
return total;
}This is O(n) time and O(1) space — you can't beat it. So recursion isn't here to be faster. It's here to teach a way of thinking that unlocks problems a plain loop can't touch, like walking a binary tree or exploring a maze. On those, "shrink the problem and call yourself" is the only clean move. Learning it on array-sum, where you can check every step by hand, is the whole point.
The key insight: shrink by one, trust the recursion
Recursion works when you can express a problem in terms of a smaller version of itself. For summing an array up to index i, the smaller version is the sum up to index i - 1:
sum(arr, i) = arr[i] + sum(arr, i - 1)That single line is the recursive step. Read it as: "take the current element, then let a copy of me handle everything to its left."
But that formula recurses forever unless something stops it. That something is the base case: when the index falls below 0, there are no elements left, so the sum is 0. Return that, and the chain of deferred additions finally has a number to build on.
sum(arr, -1) = 0 // base case: nothing left to addEvery recursive function needs both halves. Drop the base case and you get infinite recursion (a stack overflow). Drop the recursive step and you never shrink the problem.
The optimal solution
This mirrors the exact codeLines the visualizer steps through — index i walks from the last position down to -1:
var sumArray = function (arr, i) {
if (i < 0) return 0; // base case
return arr[i] + sumArray(arr, i - 1); // recursive step
};
// call it starting at the last index
sumArray([3, 1, 4, 1, 5], 4); // 14The function takes the array and the index it's currently responsible for. You kick it off with i = arr.length - 1. Each call peels off arr[i], defers the addition, and asks a deeper call to sum the rest. Nothing actually gets added until the base case returns 0 — then the answers flow back up, one + at a time.
If you'd rather hide the index bookkeeping, a common wrapper starts the recursion for the caller:
function sum(arr) {
return sumArray(arr, arr.length - 1);
}Walkthrough
Trace sumArray([3, 1, 4], 2). The array is small enough to follow every frame. First the calls stack up (the descent), then they resolve bottom-up (the unwind).
| Phase | Call | i | arr[i] | Returns | Running result |
|---|---|---|---|---|---|
| Descend | sumArray(arr, 2) | 2 | 4 | waits on sumArray(arr, 1) | — |
| Descend | sumArray(arr, 1) | 1 | 1 | waits on sumArray(arr, 0) | — |
| Descend | sumArray(arr, 0) | 0 | 3 | waits on sumArray(arr, -1) | — |
| Base | sumArray(arr, -1) | -1 | — | 0 | 0 |
| Unwind | sumArray(arr, 0) | 0 | 3 | 3 + 0 | 3 |
| Unwind | sumArray(arr, 1) | 1 | 1 | 1 + 3 | 4 |
| Unwind | sumArray(arr, 2) | 2 | 4 | 4 + 4 | 8 |
The descent does no arithmetic at all — every call is paused, holding its arr[i] and waiting. The base case returning 0 is the trigger: it's the seed the whole tower of deferred additions was waiting for. Then each frame pops off the stack, adds its element to what came back, and hands the result up. The final answer, 8, is 4 + (1 + (3 + 0)).
Complexity
| Metric | Value | Why |
|---|---|---|
| Time | O(n) | one call per element, constant work in each |
| Space | O(n) | n + 1 frames live on the call stack at peak depth |
The loop version and the recursive version do the same amount of work — O(n) additions. The difference is space. A loop uses O(1) extra memory; recursion holds one stack frame per pending call, so at the deepest point (the base case) all n + 1 frames coexist. That's why a recursive sum over a multi-million-element array can overflow the stack while the loop shrugs it off.
Common mistakes
- Missing or wrong base case.
if (i < 0) return 0is the stop sign. Writingi <= 0skipsarr[0]entirely (undercounts by the first element); omitting it recurses past-1forever until the stack overflows. - Recursing without shrinking. The recursive call must be
sumArray(arr, i - 1). Passingiunchanged, ori + 1, never approaches the base case — instant infinite recursion. - Starting the index wrong. Kick off with
arr.length - 1, notarr.length. Starting atarr.lengthreadsarr[arr.length], which isundefined, andundefined + anythingisNaN. - Assuming it's faster than a loop. It isn't. Both are O(n) time, but recursion adds O(n) stack space and function-call overhead. Reach for it to learn the pattern or when the structure is genuinely recursive — not to speed up a flat array sum.
Where this pattern shows up next
The "base case plus shrink-by-one" skeleton you just built is the template for a whole family of recursion problems:
- Sum of First N Numbers — the same descent, but you shrink a counter
ninstead of an array index. - Factorial of N — swap the
+for a*and the base case returns1instead of0. - Power of Two — recursion that halves the input each step instead of decrementing by one.
- Recursion Masterclass — the full mental model behind base cases, the call stack, and when recursion earns its keep.
You can also step through the Sum of All Numbers in Array visualizer to watch the call stack grow on the descent and drain on the unwind, one frame at a time.
FAQ
Why use recursion to sum an array when a loop is simpler?
For array-sum specifically, a loop is better in production — it's O(1) space versus recursion's O(n) stack, and it avoids function-call overhead. Recursion is worth learning here because array-sum is the simplest possible place to see a base case and a recursive step working together. Once the pattern clicks on something you can verify by hand, it transfers directly to problems where recursion is the natural fit — tree traversals, backtracking, and divide-and-conquer — where a plain loop would be far messier.
What is the base case in recursive array sum?
The base case is if (i < 0) return 0. When the index drops below zero, there are no elements left to add, so the sum of "nothing" is 0. That returned zero is what every deferred addition builds on as the call stack unwinds. Without a correct base case the recursion never stops and you get a stack overflow, which is why it's the first line of the function.
What is the time and space complexity of recursive array sum?
Time is O(n): each of the n elements triggers exactly one recursive call doing constant work. Space is O(n) because the call stack holds one frame per pending call, and at the deepest point — when the base case fires — all n + 1 frames are alive at once. The iterative loop matches the O(n) time but uses only O(1) extra space, which is why very large arrays can overflow the recursive version's stack.
Why does no addition happen until the base case is reached?
Each recursive call returns arr[i] + sumArray(arr, i - 1), and the right side must finish before the + can run. So every call on the way down pauses, holding its arr[i], and waits for the deeper call to produce a value. Only the base case returns an actual number (0) without waiting. That unblocks the shallowest paused call, which adds its element and returns, unblocking the next one up — the additions all happen during the unwind, in reverse order of the calls.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.