Nitin Bansal
Posted on November 25, 2024
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:
- Base Case: A query that initializes the recursion.
- Recursive Case: A query that refers to the CTE itself to generate subsequent rows.
-
Termination Condition: Ensures the recursion stops, typically with a
WHEREclause.
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😎
Posted on November 25, 2024
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.