Unrolling recurrences: linear and quadratic cost
A recurrence counts the work of a recursion. T(n) = T(n-1) + 1 unrolls to n+1 (linear scan), T(n) = T(n-1) + n unrolls via Gauss to n(n+1)/2 (quadratic). Unroll 3-4 steps, spot the pattern, sum, sanity-check a small n.
A batch importer sails through code review: process the first item, filter it out of the list, recurse on the rest. On staging it chews 200 test records instantly. On launch night it meets 100,000 real records — and the progress bar settles in for the weekend. Nobody wrote a slow line; every single call does honest, fast work. The killer hides in the shape: each call re-scans everything that remains, so the calls do n, then n−1, then n−2 steps — and those steps add up to about five billion. Could you have seen this coming without running it? Yes — in one line of arithmetic. A recurrence is the price tag of a recursion, and unrolling it is the skill of reading the tag before the checkout.
After this lesson you can write the recurrence for a recursive function, unroll it to a closed form for the linear and quadratic shapes, apply Gauss’s pairing formula, and verify your answer with a call counter.
Write T(n) for the number of basic steps a recursive function performs on an input of size n. Because a recursive function is “one layer of my own work, plus a smaller self”, its cost obeys the same shape — a recurrence:
T(n) = T(smaller) + (work this layer)To solve a recurrence, unroll it: substitute the right-hand side into itself a few times, spot the emerging pattern, then sum everything.
The two moves are always the same regardless of the shape — write the equation off the code, then unroll until the pattern is obvious.
The recursive sum of a list makes one addition and one comparison per call — a constant, call it 1 step — then recurses on a list shorter by one:
T(n) = T(n-1) + 1, T(0) = 1Unroll:
T(n) = T(n-1) + 1
= (T(n-2) + 1) + 1 = T(n-2) + 2
= (T(n-3) + 1) + 2 = T(n-3) + 3
…pattern: T(n-k) + k
= T(0) + n = n + 1 (set k = n to reach the base)Linear: a list of a million takes about a million steps. The method never changes — unroll 3–4 steps, spot the pattern, sum it, sanity-check a small n by hand.
Check: T(2) should be 3 — and sum([a, b]) makes three calls: two elements plus the empty-list base case.
▸lesson.inset.note
The sanity check deserves to be code. The formula predicts the call count, so count the calls in a quick script — an empirical check this cheap should accompany every recurrence you solve.
Now the importer from the Hook. Each call handles one record — but first it re-scans all remaining records to filter the list. The work this layer is not constant; it is proportional to the current size:
T(n) = T(n-1) + nUnroll:
T(n) = T(n-1) + n
= T(n-2) + (n-1) + n
= T(n-3) + (n-2) + (n-1) + n
…pattern: T(0) + 1 + 2 + … + nSo the price is 1 + 2 + … + n. Carl Friedrich Gauss paired the ends: 1 + 100 = 101, 2 + 99 = 101 — fifty such pairs, total 5050. In general the n numbers form n/2 pairs each worth n + 1:
1 + 2 + … + n = n(n + 1) / 2Roughly n²/2 — quadratic. The number sense is brutal: n = 200 costs ~20,000 steps (staging shrugs); n = 100,000 costs ~5,000,000,000 steps (launch night dies).
function process(items) {
if (items.length === 0) return;
handle(items[0]);
const rest = items.filter((x) => x.id !== items[0].id); // n work per layer
process(rest); // T(n-1)
}The fix: make the per-layer work constant again — index by position instead of filtering — and the recurrence collapses back to T(n-1) + 1.
Five moves, every time:
- Write the recurrence off the code — what does one call cost, what does it recurse on?
- Unroll three or four steps mechanically by substitution.
- Spot the pattern and write the k-th step.
- Choose k so the base case is reached, and sum what accumulated.
- Sanity-check a small n by hand or with a call counter.
Five minutes of arithmetic, and the launch-night surprise becomes a review comment: this filter makes the importer quadratic — 5·10⁹ steps at prod size.
▸More practice
Run the checklist on T(n) = T(n-1) + n mentally: the k-th step is T(0) + 1 + 2 + … + n; set k = n to hit T(0) = 0; sum with Gauss to get n(n+1)/2. Sanity-check: T(3) = 1 + 2 + 3 = 6. Confirmed.
The function below recursively sums a list. T(3) = 3 + 1 = 4 — four total calls.
let calls = 0;
function sum(list) {
calls++;
if (list.length === 0) return 0;
return list[0] + sum(list.slice(1));
}
sum([5, 2, 9]);
console.log(calls); // 4 — matches T(3) = 3 + 1Trace: sum([5,2,9]) → sum([2,9]) → sum([9]) → sum([]) — four calls, hitting the base on the fourth. The formula T(n) = n + 1 with n = 3 gives exactly 4. The counter confirms the arithmetic.
A function that re-scans the remaining items on every recursive call follows T(n) = T(n-1) + n. What growth class is this?
A recurrence counts the work of a recursion: T(n) equals the work of one layer plus the cost of the smaller self it calls. The solving craft never changes — unroll three or four steps by substitution, spot the k-th-step pattern, choose k to hit the base case, sum what accumulated, and sanity-check a small n by hand or with a call counter. Two shapes cover the most common bugs. T(n) = T(n-1) + 1 unrolls to n + 1: linear, the honest scan. T(n) = T(n-1) + n is the importer repainting the fence: the sum 1 + 2 + … + n, which Gauss’s end-pairing collapses to n(n+1)/2 — quadratic, the shape that breezes through 200-row staging and burns five billion steps on 100,000 prod records. The next lesson covers the halving and two-call shapes — logarithmic, n·log n, and exponential — which complete the map.
Practice
Start at the top. Tasks go easiest → hardest: recall a fact, apply it to a case, then a senior-level stretch. Open one, attempt it, then reveal.
Something unclear?
Ask a question about this lesson. Questions are anonymous and go straight to the author to make the lesson better.