Fibonacci sequence using SQL Server CTE

• Download SqlServerFibonacci.zip - 599 B

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

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:

-----------------------------------------------------------------
-- 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

• 27^th August, 2014: Created.
• 28^th August, 2014: Data examples added, few explanations clarified.