SQLite Basics: Walk Sequences and Trees with Recursive CTEs

A recursive common table expression starts with a small result and repeatedly derives more rows from it. Use one for a sequence, a hierarchy, or reachable nodes in a graph. Unlike an ordinary CTE, its recursive query reads its own name. WITH support arrived in SQLite 3.8.3.

Prepare a scratch directory

Tested on Linux with Python 3.12.14 and SQLite 3.53.1. You need Bash, Python 3 with SQLite support, a text editor, and mktemp, rm, and rmdir. No additional Python packages are needed. Keep the same terminal open and save files as UTF-8.

start_dir="$PWD"
work_dir="$(mktemp -d)" || exit 1
cd -- "$work_dir" || exit 1

The standalone SQLite CLI was unavailable on the test machine. Save this runner as run-sql.py. Each invocation uses a fresh in-memory database and prints pipe-separated rows, displaying missing values as NULL. The toy database disappears when the connection closes. Put each statement’s ending semicolon at the end of a line, as shown; do not put two complete statements on one line. This is a teaching runner, not a general SQL shell or CSV exporter.

from pathlib import Path
import sqlite3
import sys

connection = sqlite3.connect(":memory:", isolation_level=None)
try:
    statement = ""
    for line in Path(sys.argv[1]).read_text(encoding="utf-8").splitlines(True):
        statement += line
        if sqlite3.complete_statement(statement):
            cursor = connection.execute(statement)
            for row in cursor:
                print("|".join("NULL" if value is None else str(value) for value in row))
            statement = ""
    if statement.strip():
        raise ValueError("Unfinished SQL statement")
finally:
    connection.close()

1. Generate a bounded sequence

Save as number-sequence.sql:

WITH RECURSIVE numbers(n) AS (
    VALUES (1)
    UNION ALL
    SELECT n + 1 FROM numbers WHERE n < 4
    LIMIT 100
)
SELECT n, n * n AS square FROM numbers ORDER BY n;

Run:

python3 run-sql.py number-sequence.sql

Output:

1|1
2|4
3|9
4|16

VALUES supplies the starting row, often called the anchor. The recursive SELECT adds one while the current number is below four. The WHERE condition is the normal stopping rule; LIMIT 100 inside the CTE provides an additional cap on its total rows, including the anchor.

Keep a clear termination rule before running a recursive query on unfamiliar data. A cap protects this exercise, but silently stopping at a cap can make a real report incomplete. Treat such truncation as a condition to detect, not as proof that every row was found.

2. List descendants with their depth

Save as folder-tree.sql:

CREATE TABLE folders (id INTEGER PRIMARY KEY, parent_id INTEGER, name TEXT);
INSERT INTO folders VALUES
    (1, NULL, 'Project'), (2, 1, 'Docs'), (3, 1, 'Tests'), (4, 2, 'Guides');
WITH RECURSIVE tree(id, name, depth) AS (
    SELECT id, name, 0 FROM folders WHERE id = 1
    UNION ALL
    SELECT folders.id, folders.name, tree.depth + 1
    FROM folders JOIN tree ON folders.parent_id = tree.id
    WHERE tree.depth < 10
)
SELECT id, name, depth FROM tree ORDER BY depth, id;

Run:

python3 run-sql.py folder-tree.sql

Output:

1|Project|0
2|Docs|1
3|Tests|1
4|Guides|2

The starting folder has depth zero. Joining parent_id to the current tree row finds its children and increments their depth. ORDER BY in the final SELECT defines display order; do not assume the engine’s traversal order is a reporting contract.

The depth guard stops this example after depth ten, but it is not cycle detection. A corrupt hierarchy could repeat a folder at several depths before stopping. It also omits legitimate deeper descendants. Validate the hierarchy or explicitly track visited nodes when a complete path report is required.

3. Avoid revisiting nodes in a cyclic graph

Save as reachable-nodes.sql:

CREATE TABLE edges (source TEXT, destination TEXT);
INSERT INTO edges VALUES ('a', 'b'), ('b', 'c'), ('c', 'a'), ('b', 'd');
WITH RECURSIVE reachable(node) AS (
    VALUES ('a')
    UNION
    SELECT edges.destination
    FROM edges JOIN reachable ON edges.source = reachable.node
)
SELECT node FROM reachable ORDER BY node;

Run:

python3 run-sql.py reachable-nodes.sql

Output:

a
b
c
d

There is a cycle from a to b to c and back to a. UNION discards repeated rows, so the one-column set of reachable nodes eventually stops growing. UNION ALL would keep revisiting the cycle without another stopping rule.

Deduplication applies to the entire CTE row. If you add a changing depth or path column, revisiting a at another depth creates a different row, and UNION alone no longer solves the cycle. This query answers which nodes are reachable, including the starting node; it does not calculate shortest routes.

See SQLite’s WITH clause reference for recursion and queue behavior. Start with a tiny fixture containing a leaf, a branch, and, where relevant, a cycle before applying a recursive query to a larger dataset.

Clean up

In the same terminal, remove only these example files and the empty scratch directory:

rm -- run-sql.py number-sequence.sql folder-tree.sql reachable-nodes.sql
cd -- "$start_dir" || exit 1
rmdir -- "$work_dir"
unset start_dir work_dir

Acknowledgements

This post was created with assistance from AI.