Recursive CTEs

You will be able to walk a table into itself: down or up a tree, through a graph without looping forever, and along a generated series, carrying a value so the outer query can total it.

The CTE lesson named a query; a recursive CTE is a named query that refers to itself. Set Operations showed how UNION and UNION ALL treat duplicates; here that choice decides whether a walk ends and whether every path counts.

Anchor, recursive step, and the stop

WITH RECURSIVE countdown(n) AS (
    SELECT 3                                -- anchor: the starting rows
    UNION ALL
    SELECT n - 1 FROM countdown WHERE n > 1 -- recursive step
)
SELECT n FROM countdown;

It prints 3, 2, 1. The engine works in passes. The anchor runs once and produces {3}. Each later pass runs the recursive step against only the rows the previous pass added and appends what it returns. Pass 1 sees 3 and adds 2; pass 2 sees 2 and adds 1; pass 3 sees 1, the WHERE rejects it, nothing is added, and the walk stops. Two restrictions: the CTE name appears exactly once in the recursive step's FROM, and that step may not aggregate (SUM there fails with "recursive aggregate queries not supported"). Aggregate in the outer query instead.

Walking a hierarchy

Each staff row points at its boss.

-- staff(id, name, boss_id): (1,'Ines',NULL) (2,'Omar',1) (3,'Pia',1) (4,'Quin',2) (5,'Rae',4)

Down: start at the root and join staff to the rows found so far. Carrying depth and a path string costs nothing:

WITH RECURSIVE chain(id, name, depth, path) AS (
    SELECT id, name, 0, name FROM staff WHERE boss_id IS NULL
    UNION ALL
    SELECT s.id, s.name, c.depth + 1, c.path || '>' || s.name
    FROM staff s JOIN chain c ON s.boss_id = c.id
)
SELECT depth || '|' || path FROM chain ORDER BY path;

0|Ines
1|Ines>Omar
2|Ines>Omar>Quin
3|Ines>Omar>Quin>Rae
1|Ines>Pia

Up is the join reversed: start at Rae and join each found row's boss_id to a staff id, giving Rae, Quin, Omar, Ines.

UNION versus UNION ALL, and cycles

UNION ALL keeps every row the step returns. UNION drops any row identical to one already produced, which matters in two situations.

Two paths to one node: with lanes holding s>x, s>y, x>t, y>t, a walk from s reaches t twice:

UNION ALL: s, x, y, t, t
UNION:     s, x, y, t

A cycle: with links holding a>b, b>c, c>a, a walk from a with UNION ALL returns a, b, c, a, b, c, ... and never finishes. With UNION the second a is a duplicate, the pass adds nothing, and the walk ends with a, b, c.

The trap: UNION only ends the walk if the rows are truly identical. Carry depth or path and every revisit is a new row, so the loop returns. Guard it yourself by refusing nodes already on the trail:

WITH RECURSIVE walk(node, trail) AS (
    SELECT 'a', 'a'
    UNION ALL
    SELECT dst, trail || dst FROM links JOIN walk ON src = node
    WHERE instr(trail, dst) = 0
)
SELECT trail FROM walk;

a
ab
abc

While developing, add LIMIT 20 to the outer query: SQLite stops pulling rows once it has enough, so a runaway CTE returns instead of hanging.

Series, and carrying a value

SQLite has no generate_series; a recursive CTE builds one, and a column can accumulate:

WITH RECURSIVE fact(n, f) AS (
    SELECT 1, 1
    UNION ALL
    SELECT n + 1, f * (n + 1) FROM fact WHERE n < 5
)
SELECT n || '|' || f FROM fact;

1|1
2|2
3|6
4|24
5|120

SELECT SUM(f) FROM fact then gives 153: the recursion produces rows, the outer query totals them. Dates work the same way, with date(d, '+1 day') as the step. An ORDER BY inside the recursive step picks which queued row is processed next. On staff, ORDER BY depth DESC there yields Ines, Omar, Quin, Rae, Pia (depth-first); plain ORDER BY depth yields Ines, Omar, Pia, Quin, Rae (breadth-first).

Common mistakes

• Using UNION to "be safe" when the same value can arrive by two different routes. Identical rows collapse and a total comes out too small, with no error.
• Forgetting to carry a value down: selecting the table's own per-level column instead of combining it with the running value gives per-level numbers, not whole-walk numbers.
• Aggregating in the recursive step. It is an error; carry the value down and SUM outside.

Your exercise

Starting from one assembly, print every raw component (a part that is never itself an assembly) with the total quantity one finished unit needs. The same part can sit under several sub-assemblies: multiply along each route, add across routes. If a total comes out short, check which UNION you wrote.