---
title: 'Recursive Queries'
source: 'https://academia.sh/en/courses/advanced-sql/recursive-queries'
course: 'Advanced SQL'
language: en
updated: '2026-08-23T07:00:37+00:00'
license: 'CC BY-SA 4.0'
---

# Recursive Queries

Building the anchor and recursive members with WITH RECURSIVE, moving down and up a tree, subtree totals, what happens with no cycle guard, and sequence generation.

The previous lesson said that a common table expression can only reference expressions
defined before it, and named the one exception: an expression can reference **itself**.
This exception grows SQL's expressive power qualitatively.

Suppose a library's branches are organized as a tree: every branch has a parent branch,
and Central sits at the root. The question "every branch under Central" cannot be written
without knowing the depth of the tree — three levels need three joins, four levels need
four. Depth, though, is a property of the data and changes over time. Computations like
this, which cannot be expressed with a fixed number of joins, are written with a
**recursive common table expression**.

## The Two-Step Structure

A recursive expression starts with `WITH RECURSIVE`, and its body is made of two parts
separated by `UNION ALL`:

- **Anchor member**: the query that does not reference the expression. It produces the
  starting rows.
- **Recursive member**: the query that references the expression itself. It derives new
  rows from the rows produced in the previous round.

Evaluation proceeds as follows: the anchor member runs and its result goes into a working
table. Then the recursive member runs, but only over the rows **added in the last round**;
the rows it produces are appended to the result and become the input for the next round.
Processing stops in the round where no new row is produced. This is the query-language
counterpart of the breadth-first search from the Data Structures course: it advances
level by level.

Descending from the root of the branch tree, computing depth and path, is written with
this structure:

```bash
sqlite3 -box -header <<'SQL'
CREATE TABLE branch(id INTEGER PRIMARY KEY, name TEXT NOT NULL, parent_id INT REFERENCES branch(id));
INSERT INTO branch VALUES (1,'Central',NULL),(2,'Anadolu',1),(3,'Avrupa',1),
  (4,'Kadikoy',2),(5,'Uskudar',2),(6,'Besiktas',3),(7,'Moda',4),(8,'Bostanci',4);

WITH RECURSIVE tree(id, name, depth, path) AS (
  SELECT id, name, 0, name FROM branch WHERE parent_id IS NULL
  UNION ALL
  SELECT b.id, b.name, t.depth + 1, t.path || ' > ' || b.name
  FROM branch b JOIN tree t ON b.parent_id = t.id
)
SELECT depth, name, path FROM tree ORDER BY path;
SQL
```

```text
┌───────┬──────────┬────────────────────────────────────────┐
│ depth │   name   │                  path                  │
├───────┼──────────┼────────────────────────────────────────┤
│ 0     │ Central  │ Central                                │
│ 1     │ Anadolu  │ Central > Anadolu                      │
│ 2     │ Kadikoy  │ Central > Anadolu > Kadikoy            │
│ 3     │ Bostanci │ Central > Anadolu > Kadikoy > Bostanci │
│ 3     │ Moda     │ Central > Anadolu > Kadikoy > Moda     │
│ 2     │ Uskudar  │ Central > Anadolu > Uskudar            │
│ 1     │ Avrupa   │ Central > Avrupa                       │
│ 2     │ Besiktas │ Central > Avrupa > Besiktas            │
└───────┴──────────┴────────────────────────────────────────┘
```

The anchor member selects the root: the row with no parent branch, at depth zero. The
recursive member finds the children of every node found so far, increments the depth by
one, and extends the path string. Depth and path are values that are **not present** in
the table but accumulate while traversing; this is the real power of a recursive
expression.

Because the ordering is done with `ORDER BY path`, the output reads in tree order: each
node's own subtree comes immediately below it. The depth column rises and falls as it
goes, because the sort key is the path, not the depth.

## Moving Upward

The same structure can also be built in the opposite direction. If the direction of the
join condition is reversed, the walk goes from a node toward the root; this answers the
question "which region does this branch belong to":

```bash
sqlite3 -box -header <<'SQL'
CREATE TABLE branch(id INTEGER PRIMARY KEY, name TEXT NOT NULL, parent_id INT REFERENCES branch(id));
INSERT INTO branch VALUES (1,'Central',NULL),(2,'Anadolu',1),(3,'Avrupa',1),
  (4,'Kadikoy',2),(5,'Uskudar',2),(6,'Besiktas',3),(7,'Moda',4),(8,'Bostanci',4);

WITH RECURSIVE parent_chain(id, name, parent_id, step) AS (
  SELECT id, name, parent_id, 0 FROM branch WHERE name = 'Moda'
  UNION ALL
  SELECT b.id, b.name, b.parent_id, z.step + 1
  FROM branch b JOIN parent_chain z ON b.id = z.parent_id
)
SELECT step, name FROM parent_chain ORDER BY step;
SQL
```

```text
┌──────┬─────────┐
│ step │  name   │
├──────┼─────────┤
│ 0    │ Moda    │
│ 1    │ Kadikoy │
│ 2    │ Anadolu │
│ 3    │ Central │
└──────┴─────────┘
```

The only difference is in the join condition: descending writes `b.parent_id = t.id`,
ascending writes `b.id = z.parent_id`. The chain stops at the root, because the root's
parent branch is null and matches no row.

## Aggregating Over a Subtree

A recursive expression's result is a table; it can be joined with other tables and
grouped. The question "the total loan count within each branch's own subtree" is
answered by first producing, for every node, the nodes in its subtree, and then
aggregating over that mapping:

```bash
sqlite3 -box -header <<'SQL'
CREATE TABLE branch(id INTEGER PRIMARY KEY, name TEXT NOT NULL, parent_id INT REFERENCES branch(id));
INSERT INTO branch VALUES (1,'Central',NULL),(2,'Anadolu',1),(3,'Avrupa',1),
  (4,'Kadikoy',2),(5,'Uskudar',2),(6,'Besiktas',3),(7,'Moda',4),(8,'Bostanci',4);
CREATE TABLE member(id INTEGER PRIMARY KEY, name TEXT, branch_id INT);
CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT);
INSERT INTO member VALUES (1,'Alice',7),(2,'Ben',8),(3,'Clara',5),(4,'Derek',5),
                       (5,'Evan',6),(6,'Fiona',6),(7,'Grace',7),(8,'Hannah',5);
INSERT INTO loan VALUES
  (1,1,1,'2024-03-01','2024-03-15'),(2,3,1,'2024-03-01','2024-03-20'),
  (3,5,1,'2024-03-04','2024-03-18'),(4,7,1,'2024-03-11',NULL),
  (5,9,1,'2024-03-18','2024-03-29'),(6,2,2,'2024-03-01','2024-03-12'),
  (7,4,2,'2024-03-06','2024-03-25'),(8,6,2,'2024-03-11','2024-03-19'),
  (9,8,2,'2024-03-21',NULL),(10,1,3,'2024-03-04','2024-03-10'),
  (11,3,3,'2024-03-06','2024-03-27'),(12,10,3,'2024-03-13','2024-03-22'),
  (13,2,3,'2024-03-25',NULL),(14,5,4,'2024-03-04','2024-03-09'),
  (15,7,4,'2024-03-13','2024-03-26'),(16,4,4,'2024-03-20',NULL),
  (17,6,5,'2024-03-06','2024-03-14'),(18,9,5,'2024-03-11','2024-03-23'),
  (19,1,5,'2024-03-25','2024-03-28'),(20,8,6,'2024-03-04','2024-03-17'),
  (21,10,6,'2024-03-13','2024-03-21'),(22,3,6,'2024-03-20',NULL),
  (23,2,7,'2024-03-11','2024-03-16'),(24,5,7,'2024-03-18','2024-03-24'),
  (25,4,8,'2024-03-13','2024-03-24');

WITH RECURSIVE subtree(root_id, id) AS (
  SELECT id, id FROM branch
  UNION ALL
  SELECT a.root_id, b.id FROM branch b JOIN subtree a ON b.parent_id = a.id
)
SELECT r.name AS branch, COUNT(l.id) AS subtree_total
FROM subtree a
JOIN branch r ON r.id = a.root_id
LEFT JOIN member m ON m.branch_id = a.id
LEFT JOIN loan l ON l.member_id = m.id
GROUP BY a.root_id, r.name
ORDER BY subtree_total DESC, r.name;
SQL
```

```text
┌──────────┬───────────────┐
│  branch  │ subtree_total │
├──────────┼───────────────┤
│ Central  │ 25            │
│ Anadolu  │ 19            │
│ Kadikoy  │ 11            │
│ Uskudar  │ 8             │
│ Moda     │ 7             │
│ Avrupa   │ 6             │
│ Besiktas │ 6             │
│ Bostanci │ 4             │
└──────────┴───────────────┘
```

Here the anchor member does not take a single root but treats **every** branch as the
root of its own subtree. The result is a mapping of "which node belongs to which
subtree." The numbers are internally consistent: Kadikoy's 11 transactions are the sum of
Moda's 7 and Bostanci's 4; Anadolu's 19 is the sum of Kadikoy's 11 and Uskudar's 8. The
25 at the root is every transaction in the table.

## With No Cycle Guard

Whether the branch tree is truly a tree depends on the correctness of the data. If an
update mistakenly attaches a parent branch to its own child, the structure turns into a
cyclic graph and the recursion never stops: every round reproduces the same nodes.

The block below deliberately produces this situation — Anadolu gets attached to Moda,
which is its own descendant. So the query does not run forever, a **depth limit** is
placed on the recursive member; the limit does not resolve the cycle, it only makes the
result visible:

```bash
sqlite3 -box -header <<'SQL'
CREATE TABLE branch(id INTEGER PRIMARY KEY, name TEXT NOT NULL, parent_id INT REFERENCES branch(id));
INSERT INTO branch VALUES (1,'Central',NULL),(2,'Anadolu',1),(3,'Avrupa',1),
  (4,'Kadikoy',2),(5,'Uskudar',2),(6,'Besiktas',3),(7,'Moda',4),(8,'Bostanci',4);
UPDATE branch SET parent_id = 7 WHERE id = 2;

WITH RECURSIVE tree(id, name, depth) AS (
  SELECT id, name, 0 FROM branch WHERE id = 4
  UNION ALL
  SELECT b.id, b.name, t.depth + 1
  FROM branch b JOIN tree t ON b.parent_id = t.id
  WHERE t.depth < 7
)
SELECT depth, id, name FROM tree ORDER BY depth, id;
SQL
```

```text
┌───────┬────┬──────────┐
│ depth │ id │   name   │
├───────┼────┼──────────┤
│ 0     │ 4  │ Kadikoy  │
│ 1     │ 7  │ Moda     │
│ 1     │ 8  │ Bostanci │
│ 2     │ 2  │ Anadolu  │
│ 3     │ 4  │ Kadikoy  │
│ 3     │ 5  │ Uskudar  │
│ 4     │ 7  │ Moda     │
│ 4     │ 8  │ Bostanci │
│ 5     │ 2  │ Anadolu  │
│ 6     │ 4  │ Kadikoy  │
│ 6     │ 5  │ Uskudar  │
│ 7     │ 7  │ Moda     │
│ 7     │ 8  │ Bostanci │
└───────┴────┴──────────┘
```

Kadikoy reappears at depth three and six, Moda at depth one, four, and seven. The pattern
repeats every three steps: `4 → 7 → 2 → 4`. Had the limit been removed, the query would
not have stopped; it would have kept producing rows until memory or temporary disk space
ran out.

The correct fix is to track the nodes already visited and prevent a revisit. The path
walked is accumulated in a string, and the recursive member refuses to take a node a
second time if it has already appeared in the path:

```bash
sqlite3 -box -header <<'SQL'
CREATE TABLE branch(id INTEGER PRIMARY KEY, name TEXT NOT NULL, parent_id INT REFERENCES branch(id));
INSERT INTO branch VALUES (1,'Central',NULL),(2,'Anadolu',1),(3,'Avrupa',1),
  (4,'Kadikoy',2),(5,'Uskudar',2),(6,'Besiktas',3),(7,'Moda',4),(8,'Bostanci',4);
UPDATE branch SET parent_id = 7 WHERE id = 2;

WITH RECURSIVE tree(id, name, depth, path) AS (
  SELECT id, name, 0, '/' || id || '/' FROM branch WHERE id = 4
  UNION ALL
  SELECT b.id, b.name, t.depth + 1, t.path || b.id || '/'
  FROM branch b JOIN tree t ON b.parent_id = t.id
  WHERE t.path NOT LIKE '%/' || b.id || '/%'
)
SELECT depth, id, name, path FROM tree ORDER BY depth, id;
SQL
```

```text
┌───────┬────┬──────────┬───────────┐
│ depth │ id │   name   │   path    │
├───────┼────┼──────────┼───────────┤
│ 0     │ 4  │ Kadikoy  │ /4/       │
│ 1     │ 7  │ Moda     │ /4/7/     │
│ 1     │ 8  │ Bostanci │ /4/8/     │
│ 2     │ 2  │ Anadolu  │ /4/7/2/   │
│ 3     │ 5  │ Uskudar  │ /4/7/2/5/ │
└───────┴────┴──────────┴───────────┘
```

The query stopped at five rows. The `/4/7/2/4/` step, which would have reached Kadikoy a
second time, was eliminated because `/4/` had already appeared in the path. Identifiers
are written between slashes precisely so that the `/4/` pattern is not confused with
`/14/` or `/41/`.

This guard visits every node **once per path**; in a general graph, the same node can be
reached by different paths, so the row count can still grow. When every node needs to be
visited exactly once, `UNION` — which removes duplicates — is used instead of
`UNION ALL`; its cost is a uniqueness check on every round.

## Outside a Hierarchy

The anchor member of a recursive expression does not have to come from a table. Starting
from a fixed row and applying a rule, a sequence can be generated. A typical use for this
is showing days with no data as zero in a report:

```bash
sqlite3 -box -header <<'SQL'
CREATE TABLE loan(id INTEGER PRIMARY KEY, book_id INT, member_id INT, pickup TEXT, returned TEXT);
INSERT INTO loan VALUES
  (1,1,1,'2024-03-01','2024-03-15'),(2,3,1,'2024-03-01','2024-03-20'),
  (3,5,1,'2024-03-04','2024-03-18'),(6,2,2,'2024-03-01','2024-03-12'),
  (10,1,3,'2024-03-04','2024-03-10'),(14,5,4,'2024-03-04','2024-03-09');

WITH RECURSIVE day(date) AS (
  SELECT '2024-03-01'
  UNION ALL
  SELECT date(date, '+1 day') FROM day WHERE date < '2024-03-06'
)
SELECT d.date, COUNT(l.id) AS transaction_count
FROM day d LEFT JOIN loan l ON l.pickup = d.date
GROUP BY d.date ORDER BY d.date;
SQL
```

```text
┌────────────┬───────────────────┐
│    date    │ transaction_count │
├────────────┼───────────────────┤
│ 2024-03-01 │ 3                 │
│ 2024-03-02 │ 0                 │
│ 2024-03-03 │ 0                 │
│ 2024-03-04 │ 3                 │
│ 2024-03-05 │ 0                 │
│ 2024-03-06 │ 0                 │
└────────────┴───────────────────┘
```

Had only the `loan` table been grouped, March 2nd and 3rd would not appear at all; empty
days would disappear from the report. The generated calendar forms the left side of the
left outer join and fills the missing days with zero. The name of the date function
varies by engine; what does not vary is the structure made of the anchor member and the
stopping condition.

The stopping condition has to sit **inside the recursive member**. If the condition is
written into an outer `WHERE` clause instead, generation does not stop; the outer filter
only weeds out the rows already produced. This is the most common mistake made when
writing a recursive query.

## Summary

- A recursive common table expression is made of an anchor member and a self-referencing
  recursive member joined with `UNION ALL`; it stops in the round where no new row is
  produced.
- Values like depth, path, and step number are not present in the table; they accumulate
  during the traversal.
- Reversing the direction of the join condition lets the same structure walk both the
  subtree and the parent chain.
- If the data contains a cycle, the recursion does not stop; accumulating the visited
  nodes in a path and eliminating a repeated step is the guard that terminates the query.
- The anchor member can be a fixed row; this is the standard way to generate the calendar
  that fills in missing days in reports.

## Next Step

What the computations in this lesson had in common is that the result changed the
**row set**: traversal produced new rows, grouping reduced rows to one per group. In
some questions, though, the rows should be preserved, and a value that looks at its
neighbors added next to each one — a member's running total next to that member's
transaction, up to that day. Grouping cannot do this, because grouping swallows rows. The
next lesson introduces window functions, which compute over neighboring rows while
preserving them, and shows how the frame definition changes the result within the same
query.