Recursive Patterns in Practice

Bounded Paths

Stop Recursive Search

Recursive graph queries should have a clear bound so replay stays finite and predictable.

Program

Play the script to choose a maximum hop count and list acyclic paths from a start node.

max_hops
bounded_route_paths.sql
Replay: real traced execution (multi-file project)
CREATE TABLE edges (src TEXT, dst TEXT, cost INTEGER);
INSERT INTO edges VALUES ('A', 'B', 2), ('A', 'C', 5), ('B', 'D', 3), ('C', 'D', 1), ('D', 'E', 4);
WITH RECURSIVE params(max_hops) AS (VALUES (2)), paths(node, path, cost, hops) AS (SELECT 'A', 'A', 0, 0 UNION ALL SELECT e.dst, paths.path || '>' || e.dst, paths.cost + e.cost, paths.hops + 1 FROM edges AS e JOIN paths ON e.src = paths.node WHERE paths.hops < (SELECT max_hops FROM params) AND instr(paths.path, e.dst) = 0) SELECT node, path, cost, hops FROM paths WHERE hops > 0 ORDER BY hops, path;

CREATE TABLE edges (src TEXT, dst TEXT, cost INTEGER);
INSERT INTO edges VALUES ('A', 'B', 2), ('A', 'C', 5), ('B', 'D', 3), ('C', 'D', 1), ('D', 'E', 4);
WITH RECURSIVE params(max_hops) AS (VALUES (1)), paths(node, path, cost, hops) AS (SELECT 'A', 'A', 0, 0 UNION ALL SELECT e.dst, paths.path || '>' || e.dst, paths.cost + e.cost, paths.hops + 1 FROM edges AS e JOIN paths ON e.src = paths.node WHERE paths.hops < (SELECT max_hops FROM params) AND instr(paths.path, e.dst) = 0) SELECT node, path, cost, hops FROM paths WHERE hops > 0 ORDER BY hops, path;

CREATE TABLE edges (src TEXT, dst TEXT, cost INTEGER);
INSERT INTO edges VALUES ('A', 'B', 2), ('A', 'C', 5), ('B', 'D', 3), ('C', 'D', 1), ('D', 'E', 4);
WITH RECURSIVE params(max_hops) AS (VALUES (3)), paths(node, path, cost, hops) AS (SELECT 'A', 'A', 0, 0 UNION ALL SELECT e.dst, paths.path || '>' || e.dst, paths.cost + e.cost, paths.hops + 1 FROM edges AS e JOIN paths ON e.src = paths.node WHERE paths.hops < (SELECT max_hops FROM params) AND instr(paths.path, e.dst) = 0) SELECT node, path, cost, hops FROM paths WHERE hops > 0 ORDER BY hops, path;

  1. tables ← 1 row

    1CREATE TABLE edges (src TEXT, dst TEXT, cost INTEGER);2INSERT INTO edges VALUES ('A', 'B', 2), ('A', 'C', 5), ('B', 'D', 3), ('C', 'D', 1), ('D', 'E', 4);
    values this step1 rowtables

  2. edges ← 5 rows

    1CREATE TABLE edges (src TEXT, dst TEXT, cost INTEGER);2INSERT INTO edges VALUES ('A', 'B', 2), ('A', 'C', 5), ('B', 'D', 3), ('C', 'D', 1), ('D', 'E', 4);3WITH RECURSIVE params(max_hops) AS (VALUES (2)), paths(node, path, cost, hops) AS (SELECT 'A', 'A', 0, 0 UNION ALL SELECT e.dst, paths.path || '>' || e.dst, paths.cost + e.cost, paths.hops + 1 FROM edges AS e JOIN paths ON e.src = paths.node WHERE paths.hops < (SELECT max_hops FROM params) AND instr(paths.path, e.dst) = 0) SELECT node, path, cost, hops FROM paths WHERE hops > 0 ORDER BY hops, path;
    values this step5 rowsedges

  3. result ← 4 rows

    2INSERT INTO edges VALUES ('A', 'B', 2), ('A', 'C', 5), ('B', 'D', 3), ('C', 'D', 1), ('D', 'E', 4);3WITH RECURSIVE params(max_hops) AS (VALUES (2)), paths(node, path, cost, hops) AS (SELECT 'A', 'A', 0, 0 UNION ALL SELECT e.dst, paths.path || '>' || e.dst, paths.cost + e.cost, paths.hops + 1 FROM edges AS e JOIN paths ON e.src = paths.node WHERE paths.hops < (SELECT max_hops FROM params) AND instr(paths.path, e.dst) = 0) SELECT node, path, cost, hops FROM paths WHERE hops > 0 ORDER BY hops, path;
    values this step4 rowsresult

  1. tables ← 1 row

    1CREATE TABLE edges (src TEXT, dst TEXT, cost INTEGER);2INSERT INTO edges VALUES ('A', 'B', 2), ('A', 'C', 5), ('B', 'D', 3), ('C', 'D', 1), ('D', 'E', 4);
    values this step1 rowtables

  2. edges ← 5 rows

    1CREATE TABLE edges (src TEXT, dst TEXT, cost INTEGER);2INSERT INTO edges VALUES ('A', 'B', 2), ('A', 'C', 5), ('B', 'D', 3), ('C', 'D', 1), ('D', 'E', 4);3WITH RECURSIVE params(max_hops) AS (VALUES (1)), paths(node, path, cost, hops) AS (SELECT 'A', 'A', 0, 0 UNION ALL SELECT e.dst, paths.path || '>' || e.dst, paths.cost + e.cost, paths.hops + 1 FROM edges AS e JOIN paths ON e.src = paths.node WHERE paths.hops < (SELECT max_hops FROM params) AND instr(paths.path, e.dst) = 0) SELECT node, path, cost, hops FROM paths WHERE hops > 0 ORDER BY hops, path;
    values this step5 rowsedges

  3. result ← 2 rows

    2INSERT INTO edges VALUES ('A', 'B', 2), ('A', 'C', 5), ('B', 'D', 3), ('C', 'D', 1), ('D', 'E', 4);3WITH RECURSIVE params(max_hops) AS (VALUES (1)), paths(node, path, cost, hops) AS (SELECT 'A', 'A', 0, 0 UNION ALL SELECT e.dst, paths.path || '>' || e.dst, paths.cost + e.cost, paths.hops + 1 FROM edges AS e JOIN paths ON e.src = paths.node WHERE paths.hops < (SELECT max_hops FROM params) AND instr(paths.path, e.dst) = 0) SELECT node, path, cost, hops FROM paths WHERE hops > 0 ORDER BY hops, path;
    values this step2 rowsresult

  1. tables ← 1 row

    1CREATE TABLE edges (src TEXT, dst TEXT, cost INTEGER);2INSERT INTO edges VALUES ('A', 'B', 2), ('A', 'C', 5), ('B', 'D', 3), ('C', 'D', 1), ('D', 'E', 4);
    values this step1 rowtables

  2. edges ← 5 rows

    1CREATE TABLE edges (src TEXT, dst TEXT, cost INTEGER);2INSERT INTO edges VALUES ('A', 'B', 2), ('A', 'C', 5), ('B', 'D', 3), ('C', 'D', 1), ('D', 'E', 4);3WITH RECURSIVE params(max_hops) AS (VALUES (3)), paths(node, path, cost, hops) AS (SELECT 'A', 'A', 0, 0 UNION ALL SELECT e.dst, paths.path || '>' || e.dst, paths.cost + e.cost, paths.hops + 1 FROM edges AS e JOIN paths ON e.src = paths.node WHERE paths.hops < (SELECT max_hops FROM params) AND instr(paths.path, e.dst) = 0) SELECT node, path, cost, hops FROM paths WHERE hops > 0 ORDER BY hops, path;
    values this step5 rowsedges

  3. result ← 6 rows

    2INSERT INTO edges VALUES ('A', 'B', 2), ('A', 'C', 5), ('B', 'D', 3), ('C', 'D', 1), ('D', 'E', 4);3WITH RECURSIVE params(max_hops) AS (VALUES (3)), paths(node, path, cost, hops) AS (SELECT 'A', 'A', 0, 0 UNION ALL SELECT e.dst, paths.path || '>' || e.dst, paths.cost + e.cost, paths.hops + 1 FROM edges AS e JOIN paths ON e.src = paths.node WHERE paths.hops < (SELECT max_hops FROM params) AND instr(paths.path, e.dst) = 0) SELECT node, path, cost, hops FROM paths WHERE hops > 0 ORDER BY hops, path;
    values this step6 rowsresult
bound `max_hops` limits how far the recursion can search.
path string The path column records the route taken so far.
cycle guard `instr(path, e.dst) = 0` avoids revisiting a node already in the path.