Recursive CTEs: anchor, iterate, stop

Anatomy: anchor UNION recursive term

A recursive CTE has a fixed shape. The keyword is WITH RECURSIVE, and the CTE body is two queries combined by UNION or UNION ALL:

• the anchor term — a non-recursive query that produces the starting rows (the base case);
• the recursive term — a query that references the CTE by its own name, producing the next rows from the previous ones.

Here is “all reports under Ada, with depth” against employees(id, manager_id, name):

WITH RECURSIVE subtree AS (
  -- anchor: start at Ada
  SELECT id, manager_id, name, 1 AS depth
  FROM employees
  WHERE name = 'Ada'

  UNION ALL

  -- recursive term: one level down each pass
  SELECT e.id, e.manager_id, e.name, s.depth + 1
  FROM employees e
  JOIN subtree s ON e.manager_id = s.id
)
SELECT id, name, depth FROM subtree ORDER BY depth, id;

The recursive term joins employees to subtree — the CTE referencing itself — which is the one self-reference lesson 01 said was legal only here.

The working-table execution model

Postgres does not evaluate this with mathematical recursion or function calls. It runs an iterative loop over a working table, and understanding that model is the difference between writing recursive SQL by ritual and debugging it under load:

1. Evaluate the anchor term. Put its rows into the result and into the working table.
2. Repeat: evaluate the recursive term, but with each self-reference to the CTE reading only the working table (the rows from the previous iteration, not the whole accumulated result). Append the new rows to the result; they become the new working table.
3. Stop when an iteration produces zero new rows.

Together these three steps mean each pass only ever sees fresh frontier rows, never the whole accumulating result — which is why you must carry any state you need (depth, path) inside the row itself. Without step 3’s termination condition, an infinite source of new rows means an infinite loop.

That termination rule is the whole game. The loop ends when the recursive term yields nothing — so if it always yields something, the loop never ends.

Termination, cycles, and the brake

In a clean tree (every node has one parent, no loops), recursion terminates naturally: eventually you reach the leaves and the recursive term finds no children. The danger is a cycle — a row whose chain of parents eventually points back to itself, common in edges(src, dst) graph data or a corrupted manager_id. With UNION ALL and a cycle, the loop revisits the same rows forever and the query never returns; it spins until it exhausts work_mem, spills to disk, and eventually errors or hangs. You need an explicit brake. Three options:

-- Option 1 (PG14+): the CYCLE clause does it declaratively.
WITH RECURSIVE walk AS (
  SELECT src, dst FROM edges WHERE src = 1
  UNION ALL
  SELECT e.src, e.dst FROM edges e JOIN walk w ON e.src = w.dst
)
CYCLE dst SET is_cycle USING path        -- stop revisiting a dst already on the path
SELECT * FROM walk WHERE NOT is_cycle;

-- Option 2 (any version): carry a visited-array and exclude nodes already on the path.
WITH RECURSIVE walk AS (
  SELECT src, dst, ARRAY[src] AS path FROM edges WHERE src = 1
  UNION ALL
  SELECT e.src, e.dst, w.path || e.src
  FROM edges e JOIN walk w ON e.src = w.dst
  WHERE NOT e.src = ANY(w.path)           -- don't re-enter a visited node
)
SELECT * FROM walk;

-- Option 3 (a hard cap): carry depth and bound it.
... WHERE s.depth < 50

UNION (not UNION ALL) also dedupes each pass against the accumulated result, which stops simple repeats — but it’s slower and won’t catch all graph cycles, so on real graph data prefer the explicit CYCLE clause (Postgres 14+) or a visited-array. A depth cap is the seatbelt you add regardless: even with cycle protection, an unbounded walk over a huge graph can return millions of rows, so bound the depth to something your use case actually needs.