SQL
Recursive CTEs
`WITH RECURSIVE` allows the definition of CTEs which can refer to themselves. Note that the query must be formulated in a way that ensures termination, otherwise, it may run into an infinite loop.  
#### Example: Fibonacci Sequence {#docs:sql:query_syntax:with::example-fibonacci-sequence}  
`WITH RECURSIVE` can be used to make recursive calculations. For example, here is how `WITH RECURSIVE` could be used to calculate the first ten Fibonacci numbers:  
```sql
WITH RECURSIVE FibonacciNumbers (RecursionDepth, FibonacciNumber, NextNumber) AS (
-- Base case
SELECT
0 AS RecursionDepth,
0 AS FibonacciNumber,
1 AS NextNumber
UNION ALL
-- Recursive step
SELECT
fib.RecursionDepth + 1 AS RecursionDepth,
fib.NextNumber AS FibonacciNumber,
fib.FibonacciNumber + fib.NextNumber AS NextNumber
FROM
FibonacciNumbers fib
WHERE
fib.RecursionDepth + 1 < 10
)
SELECT
fn.RecursionDepth AS FibonacciNumberIndex,
fn.FibonacciNumber
FROM
FibonacciNumbers fn;
```  
| FibonacciNumberIndex | FibonacciNumber |
|---------------------:|----------------:|
| 0                    | 0               |
| 1                    | 1               |
| 2                    | 1               |
| 3                    | 2               |
| 4                    | 3               |
| 5                    | 5               |
| 6                    | 8               |
| 7                    | 13              |
| 8                    | 21              |
| 9                    | 34              |  
#### Example: Tree Traversal {#docs:sql:query_syntax:with::example-tree-traversal}  
`WITH RECURSIVE` can be used to traverse trees. For example, take a hierarchy of tags:  
<img alt="Example tree" src="/images/examples/with-recursive-tree-example.svg" style="width: 700px; text-align: center">  
```sql
CREATE TABLE tag (id INTEGER, name VARCHAR, subclassof INTEGER);
INSERT INTO tag VALUES
(1, 'U2',     5),
(2, 'Blur',   5),
(3, 'Oasis',  5),
(4, '2Pac',   6),
(5, 'Rock',   7),
(6, 'Rap',    7),
(7, 'Music',  9),
(8, 'Movies', 9),
(9, 'Art', NULL);
```  
The following query returns the path from the node `Oasis` to the root of the tree (` Art`).  
```sql
WITH RECURSIVE tag_hierarchy(id, source, path) AS (
SELECT id, name, [name] AS path
FROM tag
WHERE subclassof IS NULL
UNION ALL
SELECT tag.id, tag.name, list_prepend(tag.name, tag_hierarchy.path)
FROM tag, tag_hierarchy
WHERE tag.subclassof = tag_hierarchy.id
)
SELECT path
FROM tag_hierarchy
WHERE source = 'Oasis';
```  
|           path            |
|---------------------------|
| [Oasis, Rock, Music, Art] |  
#### Graph Traversal {#docs:sql:query_syntax:with::graph-traversal}  
The `WITH RECURSIVE` clause can be used to express graph traversal on arbitrary graphs. However, if the graph has cycles, the query must perform cycle detection to prevent infinite loops.
One way to achieve this is to store the path of a traversal in a [list](#docs:sql:data_types:list) and, before extending the path with a new edge, check whether its endpoint has been visited before (see the example later).  
Take the following directed graph from the [LDBC Graphalytics benchmark](https://arxiv.org/pdf/2011.15028.pdf):  
<img alt="Example graph" src="/images/examples/with-recursive-graph-example.svg" style="width: 700px; text-align: center">  
```sql
CREATE TABLE edge (node1id INTEGER, node2id INTEGER);
INSERT INTO edge VALUES
(1, 3), (1, 5), (2, 4), (2, 5), (2, 10), (3, 1),
(3, 5), (3, 8), (3, 10), (5, 3), (5, 4), (5, 8),
(6, 3), (6, 4), (7, 4), (8, 1), (9, 4);
```  
Note that the graph contains directed cycles, e.g., between nodes 1, 2, and 5.