CTEs (WITH clause) — recursive CTEs: Worked examples

This page is a firing range: every kind of recursive-CTE problem the world (or an exam) can throw at you, worked from the ground up. If you have not yet met the words anchor, recursive member, working table, or the loop algorithm, read the parent note first — everything here assumes that machinery and just drives it hard.

Quick refresher of the one machine we keep using, in plain words:

Everything below is just this loop with different anchors, different join conditions, and different stop guards.

The scenario matrix

Every recursive-CTE problem lands in one of these cells. The trick is: once you can name the cell, you already know the shape of the answer.

Cell	What varies	Danger it introduces	Example that hits it
A. Linear counter	one row grows by a rule	infinite loop if no bound	Ex 1
B. Descending a tree (down)	join child → parent	none (trees can't cycle)	Ex 2
C. Ascending a tree (up)	join parent → child, one path	none	Ex 3
D. Zero / degenerate anchor	anchor returns no rows	whole result is empty	Ex 4
E. Boundary / off-by-one	where exactly does the guard fire?	one row too many/few	Ex 5
F. Cyclic graph	edges loop back	never terminates	Ex 6
G. `UNION` vs `UNION ALL`	dedupe changes the count	wrong totals, hidden rows	Ex 7
H. Real-world word problem	you must model it first	picking wrong anchor	Ex 8
I. Exam twist (aggregate over recursion)	combine with SUM/running total	reading stale $W_{i - 1}$	Ex 9

The nine examples below cover all nine cells. Each is labelled with its cell.

Ex 1 — Cell A: the linear counter (and its limiting behaviour)

Worked example Count from 3 up to 3 (yes,

to itself)

WITH RECURSIVE nums AS (
    SELECT 3 AS n
    UNION ALL
    SELECT n + 1 FROM nums WHERE n < 3
)
SELECT n FROM nums;

Forecast: how many rows come out? Guess before reading.

Steps.

Anchor runs once → $W_{0} = {3}$ , appended to $R$ . Why this step? The anchor is unconditional; it always fires exactly one time.
Round 1: recursive member reads $W_{0} = {3}$ . It checks WHERE n < 3 on the row n=3. Since $3 < 3$ is false, the row is filtered out → the recursive SELECT produces no rows. Why this step? The guard is evaluated on this round's input, not the output. Input n=3 fails, so nothing is generated.
$W_{1} = \emptyset$ → stop. Why this step? Zero new rows is the exact termination condition.

Verify. $R = {3}$ → 1 row. This is the limiting case of a counter: when the guard is already false at the anchor, you get exactly the anchor back. (Compare the parent's 1→5 which gave 5 rows because the guard stayed true four extra times.)

Ex 2 — Cell B: descend a tree, count every descendant

We reuse emp(id, name, manager_id). Look at the tree first — the figure is the derivation.

Figure s01 — what it shows (read this even if the image fails to load): a small org tree drawn top-to-bottom. Node 1 (CEO) sits at the top in blue and is labelled $W_{0}$ / lvl 1. Two orange arrows drop from node 1 to nodes 2 and 3 (the orange level, $W_{1}$ / lvl 2). Green arrows then drop to nodes 4, 5 (under 2) and 6 (under 3) — the bottom green level, $W_{2}$ / lvl 3. The colour of each row = which working table produced it; each downward arrow = one iteration of the loop.

Figure — CTEs (WITH clause) — recursive CTEs

Worked example Every person under the CEO, tagged with depth

WITH RECURSIVE chain AS (
    SELECT id, name, 1 AS lvl
    FROM emp WHERE manager_id IS NULL          -- anchor: CEO (id=1)
    UNION ALL
    SELECT e.id, e.name, c.lvl + 1
    FROM emp e JOIN chain c ON e.manager_id = c.id
)
SELECT lvl, count(*) AS people FROM chain GROUP BY lvl ORDER BY lvl;

Using the tree in the figure (CEO=1; 2,3 report to 1; 4,5 report to 2; 6 reports to 3): Forecast: how many people at each level?

Steps.

Anchor: manager_id IS NULL → only node 1. So $W_{0} = {(1, lvl 1)}$ . Why this step? NULL marks the root — the person with no boss. That is level 1 (the blue node at the top of the figure).
Round 1: join every employee e whose e.manager_id equals an id in $W_{0}$ (=1). That's nodes 2 and 3, stamped lvl = 1+1 = 2. $W_{1} = {2, 3}$ . Why this step? Each round descends exactly one edge of the tree — the two orange arrows from node 1 in the figure.
Round 2: feed $W_{1} = {2, 3}$ . Children of 2 are {4,5}; child of 3 is {6}. All stamped lvl 3. $W_{2} = {4, 5, 6}$ (the green nodes).
Round 3: feed $W_{2} = {4, 5, 6}$ . None of them is a manager → recursive member produces nothing. $W_{3} = \emptyset$ → stop. Why this step? Leaves have no children, so the join finds no matches — the tree's bottom is a natural stop guard (no WHERE needed for a finite tree).

Verify. Level counts: lvl 1 → 1, lvl 2 → 2, lvl 3 → 3. Total people $= 1 + 2 + 3 = 6$ , which matches the six nodes drawn. Units sanity: sum of per-level counts must equal total rows — it does.

Ex 3 — Cell C: climb up from one node to the root

Same tree (Figure s01), opposite direction: given employee 5, list their whole management chain up to the CEO. In the figure this is the single path 5 → 2 → 1 read bottom-to-top.

Worked example Ancestor chain of node 5

WITH RECURSIVE up AS (
    SELECT id, name, manager_id FROM emp WHERE id = 5      -- anchor: start person
    UNION ALL
    SELECT m.id, m.name, m.manager_id
    FROM emp m JOIN up u ON m.id = u.manager_id            -- jump to the boss
)
SELECT id FROM up ORDER BY id;

Forecast: which ids appear?

Steps.

Anchor: id = 5 → $W_{0} = {5}$ (whose manager_id is 2). Why this step? When ascending, the anchor is the start leaf, not the root.
Round 1: join m.id = u.manager_id, i.e. find the row whose id equals 5's manager (2). $W_{1} = {2}$ (manager 1). Why this step? We flip the join key: last round we matched children→parent id; now we match on the parent's id to hop upward one edge.
Round 2: feed {2}, its manager is 1 → $W_{2} = {1}$ (manager NULL).
Round 3: feed {1}, u.manager_id is NULL, m.id = NULL matches nothing → $W_{3} = \emptyset$ → stop. Why this step? Reaching the root (NULL parent) makes the join fail — the root is the natural terminator when climbing.

Verify. Result ids {1, 2, 5} — exactly the path 5 → 2 → 1 in the figure, read bottom-to-top. Length 3 = depth of node 5, consistent with Ex 2 (node 5 sat at lvl 3).

Ex 4 — Cell D: the degenerate anchor (empty result)

Worked example Reports of a manager who doesn't exist

WITH RECURSIVE chain AS (
    SELECT id, name FROM emp WHERE id = 999      -- no such employee
    UNION ALL
    SELECT e.id, e.name FROM emp e JOIN chain c ON e.manager_id = c.id
)
SELECT count(*) FROM chain;

Forecast: what does count(*) return — 0, NULL, or an error?

Steps.

Anchor filters id = 999 → no matching row → $W_{0} = \emptyset$ . Why this step? The anchor is still just a SELECT; if it matches nothing, it yields nothing.
Round 1: recursive member joins against $W_{0} = \emptyset$ . A join with an empty side produces zero rows → $W_{1} = \emptyset$ → stop immediately. Why this step? No seed rows means nothing can ever be discovered — the loop never even gets going.

Verify. $R = \emptyset$ , so count(*) = 0 (never NULL, never an error — COUNT of no rows is defined as 0). This is the key degenerate case: an empty anchor collapses the entire recursion, no matter how clever the recursive member is.

Ex 5 — Cell E: nail the boundary (off-by-one)

Worked example Powers of two that stay below 100

WITH RECURSIVE pow AS (
    SELECT 1 AS v
    UNION ALL
    SELECT v * 2 FROM pow WHERE v * 2 < 100
)
SELECT v FROM pow ORDER BY v;

Forecast: is 64 included? Is 128? Where exactly does it stop?

The subtlety: the guard tests v * 2 < 100, i.e. it looks at the row about to be produced, not the current one. So each round we hold one value and ask "may I emit its double?".

Steps — one round, one doubling, one reason:

Anchor: $W_{0} = {1}$ . Why this step? The seed value is the first power of two, $2^{0} = 1$ .
Round 1: input $v = 1$ . Guard 1*2 = 2 < 100? True → emit 2. $W_{1} = {2}$ . Why this step? The guard passes on the candidate 2, so it is produced and becomes next round's sole input.
Round 2: input $v = 2$ . 2*2 = 4 < 100? True → emit 4. $W_{2} = {4}$ . Why this step? Same rule on the newest row only — the working table always holds exactly last round's single value.
Round 3: input $v = 4$ . 4*2 = 8 < 100? True → emit 8. $W_{3} = {8}$ . Why this step? Still doubling, still under 100.
Round 4: input $v = 8$ . 8*2 = 16 < 100? True → emit 16. $W_{4} = {16}$ . Why this step? Candidate 16 passes the guard.
Round 5: input $v = 16$ . 16*2 = 32 < 100? True → emit 32. $W_{5} = {32}$ . Why this step? Candidate 32 passes.
Round 6: input $v = 32$ . 32*2 = 64 < 100? True → emit 64. $W_{6} = {64}$ . Why this step? Candidate 64 is the last value that still clears the bound.
Round 7: input $v = 64$ . 64*2 = 128 < 100? False → emit nothing → $W_{7} = \emptyset$ → stop. Why this step? The guard fires on the candidate 128, rejecting it, so 64 is the last survivor and 128 never appears.

Verify. Result = {1, 2, 4, 8, 16, 32, 64} — 7 rows, max is 64. Check the boundary both ways: largest included = $2^{6} = 64 < 100$ ✓; first excluded = $2^{7} = 128 \neq < 100$ ✓. Off-by-one resolved: the guard's placement on v*2 (not v) is what keeps 128 out.

Ex 6 — Cell F: a cyclic graph (why `UNION ALL` alone loops forever)

Consider edges(src,dst) with a cycle A→B, B→C, C→A. Look at it:

Figure s02 — what it shows (read this even if the image fails to load): three blue nodes A, B, C arranged in a triangle. Two green directed arrows A→B and B→C mark edges that were kept (destination not yet visited). One red arrow C→A is marked with an X and the note "A already in path" — this is the closing edge of the cycle, rejected by the guard. A side caption shows the visited path growing [A] → [A,B] → [A,B,C], and the guard rule e.dst <> ALL(path). The picture = why the loop terminates after three productive rounds.

Worked example Reachable-from-A, done safely

WITH RECURSIVE reach AS (
    SELECT 'A' AS node, ARRAY['A'] AS path
    UNION ALL
    SELECT e.dst, r.path || e.dst
    FROM edges e JOIN reach r ON e.src = r.node
    WHERE e.dst <> ALL(r.path)        -- cycle guard
)
SELECT DISTINCT node FROM reach ORDER BY node;

Forecast: which nodes are reachable, and how does the guard stop the A→B→C→A loop?

Steps.

Anchor: $W_{0} = {(A, [A])}$ .
Round 1: from A follow A→B. Is B in [A]? No → keep. $W_{1} = {(B, [A, B])}$ . Why this step? path records every node visited on the way here (green trail in the figure). <> ALL(path) means "the next node must not already be on my trail."
Round 2: from B follow B→C. C not in [A,B] → keep. $W_{2} = {(C, [A, B, C])}$ .
Round 3: from C follow C→A. Is A in [A,B,C]? Yes → guard rejects → no new row. $W_{3} = \emptyset$ → stop (red X in the figure on the closing edge). Why this step? Without the guard, C→A would reseed A, replaying the cycle forever. The visited-path is what breaks it.

Verify. Distinct reachable nodes = {A, B, C} → 3 nodes. Rounds executed = 3 productive + 1 empty = the loop is bounded by the number of nodes, exactly as expected for a graph with a per-path visited set.

Ex 7 — Cell G: `UNION` vs `UNION ALL` change the count

Two paths reach node D: A→D directly, and A→B→D. Does D appear once or twice?

Worked example Same graph, two operators, different totals

-- version ALL
WITH RECURSIVE r AS (
    SELECT 'A' AS node
    UNION ALL
    SELECT e.dst FROM edges2 e JOIN r ON e.src = r.node
) SELECT count(*) FROM r;

Edges: A→B, A→D, B→D (an acyclic diamond, no WHERE needed since it's finite). Forecast: with UNION ALL how many rows total? With UNION?

Steps (UNION ALL).

$W_{0} = {A}$ (1 row).
Round 1: A's out-edges → B, D. $W_{1} = {B, D}$ (2 rows).
Round 2: feed {B,D}. B→D gives D; D has no out-edge. $W_{2} = {D}$ (1 row).
Round 3: feed {D}, no out-edges → $W_{3} = \emptyset$ → stop. Why this step? UNION ALL never dedupes, so the second discovery of D (via B) is kept as a separate row.

Verify (UNION ALL). Rows = $1 + 2 + 1 =$ 4 (A, B, D, D). D appears twice.

Now UNION. UNION dedupes against everything already accumulated. When round 2 produces D, it's already in $R$ from round 1, so it's discarded → $W_{2} = \emptyset$ → stop one round earlier. Total distinct rows = 3 (A, B, D).

Verify (UNION). 3 rows. So the same query returns 4 vs 3 rows depending purely on the operator — this is the trap. Rule of thumb: use UNION when a re-discovered row means "already handled, stop"; use UNION ALL when every discovery is a distinct fact you must keep (and add your own guard).

Ex 8 — Cell H: a real-world word problem (model it first)

Modelling — the hardest part. Each month: new = old * 1.10 - 400. That's a linear counter (Cell A) whose "value" is a running balance. Anchor = month 1 opening balance 1000. Guard = stop once the balance would drop to 0 or below.

WITH RECURSIVE loan AS (
    SELECT 1 AS month, 1000.0 AS bal
    UNION ALL
    SELECT month + 1, bal * 1.10 - 400
    FROM loan
    WHERE bal * 1.10 - 400 > 0
)
SELECT month, bal FROM loan ORDER BY month;

Forecast: roughly how many months until it's cleared?

Steps.

Month 1: bal = 1000.
Candidate month 2 = $1000 \times 1.1 - 400 = 700$ . $700 > 0$ ✓ → row.
Month 3 = $700 \times 1.1 - 400 = 370$ . ✓ → row.
Month 4 = $370 \times 1.1 - 400 = 7$ . ✓ → row.
Candidate month 5 = $7 \times 1.1 - 400 = - 392.3$ . Not $> 0$ → guard rejects → stop. Why this step? The guard tests the next balance so we don't emit a negative opening balance.

Verify. Rows emitted (opening balances): month 1 = 1000, m2 = 700, m3 = 370, m4 = 7. Four rows. Sanity check with units: balances are ₹, monotonically decreasing (each month interest 10% < payment ₹400 relative to balance once below ~₹4000), and the loop terminates because the balance strictly falls each round — a legitimate stop guard, not an accident.

Ex 9 — Cell I: the exam twist — running total inside recursion

Exam favourite: "compute a cumulative sum via recursion." The twist is you must accumulate across rounds using only $W_{i - 1}$ .

Worked example Cumulative sum

$1 + 2 + \dots + n$ up to running total ≥ 20

WITH RECURSIVE cum AS (
    SELECT 1 AS k, 1 AS running
    UNION ALL
    SELECT k + 1, running + (k + 1)
    FROM cum
    WHERE running < 20
)
SELECT k, running FROM cum ORDER BY k;

Forecast: at which $k$ does the running total first reach or pass 20, and what is the last row emitted? Guess before reading.

Steps — each round carries the running total forward in the row itself:

Anchor: $W_{0} = {(k = 1, running = 1)}$ . Why this step? We seed both the counter $k$ and the accumulator running in one row, so no round ever needs the full history — just this single latest row.
Round 1: input $(1, 1)$ . Guard running = 1 < 20? True → emit $(k + 1, running + (k + 1)) = (2, 1 + 2 = 3)$ . $W_{1} = {(2, 3)}$ . Why this step? The new running total is old running + new k, computed purely from last round's row.
Round 2: input $(2, 3)$ . 3 < 20? True → emit $(3, 3 + 3 = 6)$ . $W_{2} = {(3, 6)}$ . Why this step? Same rule; the accumulator grows by the next integer each round.
Round 3: input $(3, 6)$ . 6 < 20? True → emit $(4, 6 + 4 = 10)$ . $W_{3} = {(4, 10)}$ . Why this step? Guard still passes on the input's running total 6.
Round 4: input $(4, 10)$ . 10 < 20? True → emit $(5, 10 + 5 = 15)$ . $W_{4} = {(5, 15)}$ . Why this step? Candidate running total 15 is produced because the input 10 cleared the guard.
Round 5: input $(5, 15)$ . 15 < 20? True → emit $(6, 15 + 6 = 21)$ . $W_{5} = {(6, 21)}$ . Why this step? Here is the gotcha: the guard checks the previous row's running (15 < 20 passes), so it emits 21 even though 21 already exceeds 20.
Round 6: input $(6, 21)$ . 21 < 20? False → emit nothing → $W_{6} = \emptyset$ → stop. Why this step? Only now, one step late, does the guard fire — because it finally sees a running total ≥ 20 on its input.

Verify. Rows: $(1, 1), (2, 3), (3, 6), (4, 10), (5, 15), (6, 21)$ → 6 rows, last running total = 21. Cross-check against the closed form $\frac{n ( n + 1 )}{2}$ : for $n = 6$ , $\frac{6 \cdot 7}{2} = 21$ ✓. The guard let one extra row through (21 ≥ 20) because it tested the previous row's running < 20 — the classic "the guard is checked one step behind" exam gotcha.

Recall Which cell is my problem?

Empty answer despite a fine recursive member? ::: Cell D — check your anchor first; an empty anchor kills everything. Query hangs forever? ::: Cell F/G — cyclic data with UNION ALL and no visited-guard. Count is double what you expected? ::: Cell G — you needed UNION (dedupe) but used UNION ALL. One row too many past your limit? ::: Cell E/I — the guard tests the candidate/previous row, so it fires "one behind."

Connections

Parent: Recursive CTEs — the engine these examples exercise
Common Table Expressions (WITH clause) — non-recursive foundation
SQL Joins — every recursive member here is a join to the base table
UNION vs UNION ALL — the star of Ex 7
Tree and Graph Data Structures — Ex 2, 3 (trees), Ex 6, 7 (graphs)
Window Functions — the non-recursive way to do Ex 9's running total
Mathematical Induction — anchor = base case, recursive member = inductive step, guard = when induction halts