Click here to Skip to main content
Click here to Skip to main content

Fibonacci sequence using SQL Server CTE

, 28 Aug 2014 CPOL
Rate this:
Please Sign up or sign in to vote.
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

F= 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:

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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Mika Wendelius
Architect
Finland Finland
I've been a programmer since mid 80's using languages like assembler, C/C++, PL/I (mainframe environment), pascal, VB (I know, I know, no comments please) and C# and utilizing different techniques and tools.
 
However I'm specialized in databases and database modeling. Mostly I have used products like Oracle (from version 6), SQL Server (from version 4.2), DB2 and Solid Server (nowadays an IBM product).
 
For the past 10+ years my main concerns have been dealing with different business processes and how to create software to implement and improve them. At my spare time (what ever that actually means) I'm also teaching and consulting on different areas of database management, development and database oriented software design.

Comments and Discussions

 
GeneralMy vote of 5 Pinmembernewton.saber29-Aug-14 4:23 
GeneralRe: My vote of 5 PinmentorMika Wendelius29-Aug-14 4:36 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.141216.1 | Last Updated 28 Aug 2014
Article Copyright 2014 by Mika Wendelius
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid