Fibonacci sequence using SQL Server CTE
Generate Fibonacci numbers using CTE
Introduction
A while ago I bumped into an article presenting different ways to generate Fibonacci numbers using different languages but SQL was missing. This tip shows one way how Fibonacci sequence cane be generated using CTE (Common Table Expression).
Background
Fibonacci numbers are named after an Italian mathematician Leonardo Fibonacci. The Fibonacci number sequence starts typicaly with numbers 0 and 1 and the new number in the sequence is defined by adding two previous numbers. So as a formula
Fn = Fn-1 + Fn-2For more information about Fibonacci numbers, see Fibonacci number.
The sequence itself is recursive. A CTE can be used to generate a recursive query thus also to generate desired amount of rows. Now the problem is how to convert the formula into a CTE query.
For background information you should be familiar with row generation using CTE. If needed, refer to Generating desired amount of rows in SQL using CTE.
The query
The query is actually quite simple. Have a look at the following:
-----------------------------------------------------------------
-- Numbers F0 through F10 in Fibonacci sequence
-----------------------------------------------------------------
WITH FibonacciNumbers (RecursionLevel, FibonacciNumber, NextNumber)
AS (
-- Anchor member definition
SELECT 0 AS RecursionLevel,
0 AS FibonacciNumber,
1 AS NextNumber
UNION ALL
-- Recursive member definition
SELECT a.RecursionLevel + 1 AS RecursionLevel,
a.NextNumber AS FibonacciNumber,
a.FibonacciNumber + a.NextNumber AS NextNumber
FROM FibonacciNumbers a
WHERE a.RecursionLevel < 10
)
-- Statement that executes the CTE
SELECT 'F' + CAST( fn.RecursionLevel AS VARCHAR) AS FibonacciOrdinal,
fn.FibonacciNumber,
fn.NextNumber
FROM FibonacciNumbers fn;
GO
The RecursionLevel column is only used as a visual aid in the result set so it has no part in the actual calculation.
The FibonacciNumber and the NextNumber are separated into different columns. The column named FibonacciNumber is the actual number in the sequence while the NextNumber is the value to be added to the FibonacciNumber during the this cycle in recursion. So this number will be the Fibonacci number during the next round.
So the query above would give the following result
FibonacciOrdinal FibonacciNumber NextNumber
---------------- --------------- ----------
F0 0 1
F1 1 1
F2 1 2
F3 2 3
F4 3 5
F5 5 8
F6 8 13
F7 13 21
F8 21 34
F9 34 55
F10 55 89
So far so good. Now lets query for the first 51 numbers (numbers F0-F50) in the sequence:
-----------------------------------------------------------------
-- Numbers F0 through F50 in Fibonacci sequence
-----------------------------------------------------------------
WITH FibonacciNumbers (RecursionLevel, FibonacciNumber, NextNumber)
AS (
-- Anchor member definition
SELECT 0 AS RecursionLevel,
0 AS FibonacciNumber,
1 AS NextNumber
UNION ALL
-- Recursive member definition
SELECT a.RecursionLevel + 1 AS RecursionLevel,
a.NextNumber AS FibonacciNumber,
a.FibonacciNumber + a.NextNumber AS NextNumber
FROM FibonacciNumbers a
WHERE a.RecursionLevel < 50
)
-- Statement that executes the CTE
SELECT 'F' + CAST( fn.RecursionLevel AS VARCHAR) AS FibonacciOrdinal,
fn.FibonacciNumber,
fn.NextNumber
FROM FibonacciNumbers fn;
Instead of returning the result set this query gives an error:
Msg 8115, Level 16, State 2, Line 28
Arithmetic overflow error converting expression to data type int.
The reason is that the data type is infered from the first row in the CTE set. Since the query has defined either 0 or 1 for the values in the columns the data type for all the columns is int. Because of this an arithmetic overflow occurs when the number values exceed the integer range.
In order to solve this the data type for the columns need to be changed. An easy way is to use CAST to define a new type for the values:
-----------------------------------------------------------------
-- Numbers F0 through F50 in Fibonacci sequence
-- with CAST
-----------------------------------------------------------------
WITH FibonacciNumbers (RecursionLevel, FibonacciNumber, NextNumber)
AS (
-- Anchor member definition
SELECT 0 AS RecursionLevel,
CAST(0 AS FLOAT) AS FibonacciNumber,
CAST(1 AS FLOAT) AS NextNumber
UNION ALL
-- Recursive member definition
SELECT a.RecursionLevel + 1 AS RecursionLevel,
a.NextNumber AS FibonacciNumber,
a.FibonacciNumber + a.NextNumber AS NextNumber
FROM FibonacciNumbers a
WHERE a.RecursionLevel < 50
)
-- Statement that executes the CTE
SELECT 'F' + CAST( fn.RecursionLevel AS VARCHAR) AS FibonacciOrdinal,
fn.FibonacciNumber,
fn.NextNumber
FROM FibonacciNumbers fn;
GO
This one runs nicely and the result set is generated like following:
FibonacciOrdinal FibonacciNumber NextNumber ---------------- --------------- ---------- F0 0 1 F1 1 1 F2 1 2 F3 2 3 F4 3 5 F5 5 8 F6 8 13 F7 13 21 F8 21 34 F9 34 55 F10 55 89 ... F48 4807526976 7778742049 F49 7778742049 12586269025 F50 12586269025 20365011074
Well what happens if we try to generate, say 1'000 numbers
-----------------------------------------------------------------
-- Numbers F0 through F1000 in Fibonacci sequence
-----------------------------------------------------------------
WITH FibonacciNumbers (RecursionLevel, FibonacciNumber, NextNumber)
AS (
-- Anchor member definition
SELECT 0 AS RecursionLevel,
CAST(0 AS FLOAT) AS FibonacciNumber,
CAST(1 AS FLOAT) AS NextNumber
UNION ALL
-- Recursive member definition
SELECT a.RecursionLevel + 1 AS RecursionLevel,
a.NextNumber AS FibonacciNumber,
a.FibonacciNumber + a.NextNumber AS NextNumber
FROM FibonacciNumbers a
WHERE a.RecursionLevel < 1000
)
-- Statement that executes the CTE
SELECT 'F' + CAST( fn.RecursionLevel AS VARCHAR) AS FibonacciOrdinal,
fn.FibonacciNumber,
fn.NextNumber
FROM FibonacciNumbers fn;
GO
Again an error is generated. This it's:
Msg 530, Level 16, State 1, Line 77 The statement terminated. The maximum recursion 100 has been exhausted before statement completion.
As described in Generating desired amount of rows in SQL using CTE the maximum amount of recursion can be controlled using MAXRECURSION hint. So in order to run the previous query, it should be modified as follows
-----------------------------------------------------------------
-- Numbers F0 through F1000 in Fibonacci sequence
-- with MAXRECURSION 0
-----------------------------------------------------------------
WITH FibonacciNumbers (RecursionLevel, FibonacciNumber, NextNumber)
AS (
-- Anchor member definition
SELECT 0 AS RecursionLevel,
CAST(0 AS FLOAT) AS FibonacciNumber,
CAST(1 AS FLOAT) AS NextNumber
UNION ALL
-- Recursive member definition
SELECT a.RecursionLevel + 1 AS RecursionLevel,
a.NextNumber AS FibonacciNumber,
a.FibonacciNumber + a.NextNumber AS NextNumber
FROM FibonacciNumbers a
WHERE a.RecursionLevel < 1000
)
-- Statement that executes the CTE
SELECT 'F' + CAST( fn.RecursionLevel AS VARCHAR) AS FibonacciOrdinal,
fn.FibonacciNumber,
fn.NextNumber
FROM FibonacciNumbers fn
OPTION (MAXRECURSION 0);
GO
This would return:
FibonacciOrdinal FibonacciNumber NextNumber ---------------- --------------- ---------- F0 0 1 F1 1 1 F2 1 2 F3 2 3 F4 3 5 F5 5 8 F6 8 13 F7 13 21 F8 21 34 F9 34 55 F10 55 89 ... F998 1,66027476624521E+208 2,68638100244853E+208 F999 2,68638100244853E+208 4,34665576869374E+208 F1000 4,34665576869374E+208 7,03303677114228E+208
Just remember that since the data type of the columns is now float, the numbers are approximate. Also for float data type, the maximum number of Fibonacci numbers is F0 through F1475.
History
- 27th August, 2014: Created.
- 28th August, 2014: Data examples added, few explanations clarified.