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-2
For 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:
WITH FibonacciNumbers (RecursionLevel, FibonacciNumber, NextNumber)
AS (
SELECT 0 AS RecursionLevel,
0 AS FibonacciNumber,
1 AS NextNumber
UNION ALL
SELECT a.RecursionLevel + 1 AS RecursionLevel,
a.NextNumber AS FibonacciNumber,
a.FibonacciNumber + a.NextNumber AS NextNumber
FROM FibonacciNumbers a
WHERE a.RecursionLevel < 10
)
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:
WITH FibonacciNumbers (RecursionLevel, FibonacciNumber, NextNumber)
AS (
SELECT 0 AS RecursionLevel,
0 AS FibonacciNumber,
1 AS NextNumber
UNION ALL
SELECT a.RecursionLevel + 1 AS RecursionLevel,
a.NextNumber AS FibonacciNumber,
a.FibonacciNumber + a.NextNumber AS NextNumber
FROM FibonacciNumbers a
WHERE a.RecursionLevel < 50
)
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:
WITH FibonacciNumbers (RecursionLevel, FibonacciNumber, NextNumber)
AS (
SELECT 0 AS RecursionLevel,
CAST(0 AS FLOAT) AS FibonacciNumber,
CAST(1 AS FLOAT) AS NextNumber
UNION ALL
SELECT a.RecursionLevel + 1 AS RecursionLevel,
a.NextNumber AS FibonacciNumber,
a.FibonacciNumber + a.NextNumber AS NextNumber
FROM FibonacciNumbers a
WHERE a.RecursionLevel < 50
)
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
WITH FibonacciNumbers (RecursionLevel, FibonacciNumber, NextNumber)
AS (
SELECT 0 AS RecursionLevel,
CAST(0 AS FLOAT) AS FibonacciNumber,
CAST(1 AS FLOAT) AS NextNumber
UNION ALL
SELECT a.RecursionLevel + 1 AS RecursionLevel,
a.NextNumber AS FibonacciNumber,
a.FibonacciNumber + a.NextNumber AS NextNumber
FROM FibonacciNumbers a
WHERE a.RecursionLevel < 1000
)
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
WITH FibonacciNumbers (RecursionLevel, FibonacciNumber, NextNumber)
AS (
SELECT 0 AS RecursionLevel,
CAST(0 AS FLOAT) AS FibonacciNumber,
CAST(1 AS FLOAT) AS NextNumber
UNION ALL
SELECT a.RecursionLevel + 1 AS RecursionLevel,
a.NextNumber AS FibonacciNumber,
a.FibonacciNumber + a.NextNumber AS NextNumber
FROM FibonacciNumbers a
WHERE a.RecursionLevel < 1000
)
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.
