Recursive CTE Example: Fibonacci Sequence

Using a recursive Common Table Expression (CTE) to generate a Fibonacci sequence in SQL is a great exercise for understanding how recursion works in SQL. Below is a detailed example that shows how to create a CTE to generate the first n numbers in the Fibonacci sequence.

Fibonacci Sequence with Recursive CTE

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1. The sequence typically starts as 0, 1, 1, 2, 3, 5, 8, and so on.

SQL Query to Generate Fibonacci Sequence

Here’s how you can write a SQL query to generate the Fibonacci sequence using a recursive CTE:

sql
WITH RECURSIVE FibonacciCTE AS (
    -- Anchor members: start with the first two numbers in the sequence
    SELECT 
        0 AS position,
        0 AS fibonacci
    UNION ALL
    SELECT 
        1,
        1
    UNION ALL
    -- Recursive member: generate the next number in the sequence
    SELECT 
        position + 1 AS position,
        f1.fibonacci + f2.fibonacci AS fibonacci
    FROM 
        FibonacciCTE f1
    INNER JOIN 
        FibonacciCTE f2 ON f1.position + 1 = f2.position
    WHERE 
        f1.position < 20 -- Set the limit to avoid infinite recursion
)
SELECT 
    position, 
    fibonacci
FROM 
    FibonacciCTE
ORDER BY 
    position;

Explanation

1. Anchor Members:

   sql
   SELECT 
       0 AS position,
       0 AS fibonacci
   UNION ALL
   SELECT 
       1,
       1

   These two queries initialize the sequence with the first two numbers: 0 and 1.

2. Recursive Member:

   sql
   SELECT 
       position + 1 AS position,
       f1.fibonacci + f2.fibonacci AS fibonacci
   FROM 
       FibonacciCTE f1
   INNER JOIN 
       FibonacciCTE f2 ON f1.position + 1 = f2.position
   WHERE 
       f1.position < 20 -- Set the limit to avoid infinite recursion

   This part of the CTE generates the next number in the sequence by summing the two preceding numbers. It uses a self-join on the CTE to get the preceding two numbers. The WHERE clause ensures that the recursion stops after generating 20 numbers.

3. Final Select:

   sql
   SELECT 
       position, 
       fibonacci
   FROM 
       FibonacciCTE
   ORDER BY 
       position;

   This selects and orders the results by the position in the sequence.

Adjusting the Limit

To generate more numbers in the Fibonacci sequence, simply adjust the limit in the WHERE clause. For example, to generate the first 30 numbers, change f1.position < 20 to f1.position < 30.

Result

The result will be a table listing the positions and the corresponding Fibonacci numbers:

 position | fibonacci
----------|-----------
        0 | 0
        1 | 1
        2 | 1
        3 | 2
        4 | 3
        5 | 5
        6 | 8
        7 | 13
        8 | 21
        9 | 34
       10 | 55
       11 | 89
       12 | 144
       13 | 233
       14 | 377
       15 | 610
       16 | 987
       17 | 1597
       18 | 2584
       19 | 4181
       20 | 6765

In this example, the Fibonacci sequence starts from position 0 and generates up to position 20. The query can be adjusted to generate as many numbers in the sequence as needed.