I have listened to the critique in the comments and removed the advanced version where you can calculate virtually any Fibonacci number. Contact me if you have the need for it again. I won't bother non-interested people with the algorithm here.
Instead, I am concentrating on how this
easy example of how to use
recursive CTE for calculating the Fibonacci series is constructed.
This is done as an easy exercise for students how to implement a recursive CTE, because the results can be confirmed visually.
Understanding recursive queries is not natural for many people.
For those of you not familiar with Fibonacci series and wonder what uses does it have, I can tell that Fibonacci series is used in a number of areas
- Run-time analysis of Euclid's algorithm to determine the greatest common divisor of two integers (the worst case input for this algorithm is a pair of consecutive Fibonacci numbers
- The Fibonacci numbers and principle is also used in the financial markets. It is used in trading algorithms, applications and strategies.
- Fibonacci numbers are used by some pseudorandom number generators.
- Fibonacci numbers are used in a polyphase version of the merge sort algorithm in which an unsorted list is divided into two lists whose lengths correspond to sequential Fibonacci numbers.
- The Fibonacci cube is an undirected graph with a Fibonacci number of nodes that has been proposed as a network topology for parallel computing.
- A one-dimensional optimization method, called the Fibonacci search technique, uses Fibonacci numbers.
- The Fibonacci number series is used for optional lossy compression in the IFF 8SVX audio file format used on Amiga computers
So how is the Fibonacci series built?
The matemathical formula is F(n) = F(n-1) + F(n-2), which in plain english is that any Fibonacci number (greater than 2) is the sum of the two previous numbers.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 etc..
So how do we solve this using a recursive CTE (CTE is an acronym for Common Table Expression which was introduced with Microsof SQL Server 2005)?
Can we solve it at all? A recursive query is nested only one level, right? And the Fibonacci series is "nested" two level?
Yes, we can solve it by using a complementary "sideways" translation, a sort of intermediate storage. First thing, all recursive CTE need an anchor part, a fixed part from which the recursion is expanded from. I do this by using the values {0, 1} which per definition are the two first values of the Fibonacci series.
How is then the recursive part done? I use the two values from the previous iteration and sum them together for the next Fibonacci value. I store that value in a column, shift the columns, and use the previous value in the same recursion level. Easy, huh?
;WITH Fibonacci(n, f, f1)
AS (
-- This is the anchor part
-- Initialize level to 1 and set the first two values as per definition
SELECT CAST(1 AS BIGINT),
CAST(0 AS BIGINT),
CAST(1 AS BIGINT)
UNION ALL
-- This is the recursive part
-- Calculate the next Fibonacci value using the previous two values
-- Shift column (place) for the sum in order to accomodate the previous
-- value too because next iteration need them both
SELECT n + 1,
f + f1,
f
FROM Fibonacci
-- Stop at iteration 93 because we than have reached maximum limit
-- for BIGINT in Microsoft SQL Server
WHERE n < 93
)
-- Now the easy presentation part
SELECT n,
f AS Number
FROM Fibonacci