The Amazing SQL Recursive Queries

Basics of Recursive Queries

Recursive queries are built using Common Table Expressions (CTEs) with the WITH RECURSIVE clause. These queries are powerful tools for solving problems that require iterative or hierarchical processing, such as:

• Traversing trees or graphs.
• Generating series or grids.
• Performing iterative calculations.

A recursive CTE consists of:

1. Base Case: A query that initializes the recursion.
2. Recursive Case: A query that refers to the CTE itself to generate subsequent rows.
3. Termination Condition: Ensures the recursion stops, typically with a WHERE clause.

General Structure:

WITH RECURSIVE cte_name(columns) AS (
    -- Base Case
    SELECT initial_values
    UNION ALL
    -- Recursive Case
    SELECT derived_values FROM cte_name
    WHERE termination_condition
)
SELECT * FROM cte_name;

---

Examples

Do note we'll be using SQLite in below examples. To play around with these, go here, upload any dummy csv file and start querying.

Example 1: Generate a Sequence

SQLite Query:

WITH RECURSIVE sequence(n) AS (
    SELECT 1 -- Base case
    UNION ALL
    SELECT n + 1 FROM sequence WHERE n < 10 -- Recursive case
)
SELECT * FROM sequence;

Python Equivalent:

sequence = []
n = 1
while n <= 10:
    sequence.append(n)
    n += 1

print(sequence)

Output:

1
2
3
4
5
6
7
8
9
10

Explanation:
The query starts with n=1 and keeps adding 1 until n=10. The Python code uses a simple while loop to achieve the same.

---

Example 2: Fibonacci Sequence

SQLite Query:

WITH RECURSIVE fib(a, b) AS (
    SELECT 0, 1 -- Base case
    UNION ALL
    SELECT b, a + b FROM fib WHERE a + b < 100 -- Recursive case
)
SELECT a FROM fib;

Python Equivalent:

fib = [0, 1]
while fib[-1] + fib[-2] < 100:
    fib.append(fib[-1] + fib[-2])

print(fib)

Output:

0
1
1
2
3
5
8
13
21
34
55
89

Explanation:
The query generates Fibonacci numbers less than 100. Python uses a list to store the sequence and appends the sum of the last two elements until the condition is met.

---

Example 3: Factorial Calculation

SQLite Query:

WITH RECURSIVE factorial(n, fact) AS (
    SELECT 1, 1 -- Base case
    UNION ALL
    SELECT n + 1, fact * (n + 1) FROM factorial WHERE n < 5 -- Recursive case
)
SELECT fact FROM factorial;

Python Equivalent:

n, fact = 1, 1
factorials = [fact]
while n < 5:
    n += 1
    fact *= n
    factorials.append(fact)

print(factorials)

Output:

1
2
6
24
120

Explanation:
The query calculates factorials for numbers from 1 to 5. Python uses a loop to multiply fact by n iteratively.

---

Example 4: Sum of Numbers

SQLite Query:

WITH RECURSIVE sum_series(n, total) AS (
    SELECT 1, 1 -- Base case
    UNION ALL
    SELECT n + 1, total + n + 1 FROM sum_series WHERE n < 10 -- Recursive case
)
SELECT total FROM sum_series;

Python Equivalent:

n, total = 1, 1
sums = [total]
while n < 10:
    n += 1
    total += n
    sums.append(total)

print(sums)

Output:

1
3
6
10
15
21
28
36
45
55

Explanation:
The query calculates cumulative sums from 1 to 10. Python mimics this behavior with a loop, maintaining a running total.

---

Example 5: Binary Tree Traversal

SQLite Query:

WITH RECURSIVE binary_tree(val, level) AS (
    SELECT 1, 1 -- Base case
    UNION ALL
    SELECT val * 2, level + 1 FROM binary_tree WHERE level < 4 -- Left child
    UNION ALL
    SELECT val * 2 + 1, level + 1 FROM binary_tree WHERE level < 4 -- Right child
)
SELECT * FROM binary_tree ORDER BY level, val;

Python Equivalent:

def generate_tree(val, level, max_level, tree):
    if level > max_level:
        return
    tree.append((val, level))
    generate_tree(val * 2, level + 1, max_level, tree)  # Left child
    generate_tree(val * 2 + 1, level + 1, max_level, tree)  # Right child

tree = []
generate_tree(1, 1, 4, tree)
tree.sort(key=lambda x: (x[1], x[0]))
print(tree)

Output:

(1, 1)
(2, 2)
(3, 2)
(4, 3)
(5, 3)
(6, 3)
(7, 3)
(8, 4)
...

Explanation:
This query builds a binary tree with values doubling for left children and +1 for right children. Python uses recursion to generate the tree.

---

Super powerful, isn't it😎