12,403,811 members (68,490 online)
Tip/Trick
alternative version

13.5K views
6 bookmarked
Posted

# Fibonacci sequence using SQL Server CTE

, 28 Aug 2014 CPOL
 Rate this:
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

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.

## Share

 Architect Finland
No Biography provided

## You may also be interested in...

 First Prev Next
 My vote of 5 newton.saber29-Aug-14 3:23 newton.saber 29-Aug-14 3:23
 Re: My vote of 5 Mika Wendelius29-Aug-14 3:36 Mika Wendelius 29-Aug-14 3:36
 Last Visit: 31-Dec-99 18:00     Last Update: 28-Jul-16 10:11 Refresh 1