Fibonacci Sequence

As part of my CTE research for my SQL Saturday presentation in Redmond in 2 weeks I decided to take on some classic computer science algorithms with CTE’s. Here is what I cam up with.

Any math geek can tell you what the Fibonacci Sequence is, but do you know how to calculate it with a query?

First, what is the Fibonacci Sequence?

Fibonacci Sequence as a Computer Science Challenge

Often times calculating the Fibonacci Sequence is used as a computer science puzzle, or programming interview question to see if you understand recursion.  It is very simple to do in any programming language that supports recursion.

So what is recursion…  Recursion is a method of programming where a function ends up calling back into itself.

Writing a query to calculate the Fibonacci Sequence

In order to do this you need to understand recursion and CTE‘s.

The following query uses a recursive CTE query to generate the fibonacci sequence.

— Calculating the Fibonacci sequence WITH Fibonacci (PrevN, N) AS

( SELECT 0, 1

UNION ALL

SELECT N, PrevN + N

FROM Fibonacci

WHERE N < 1000000000

)

SELECT PrevN as Fibo

FROM Fibonacci

OPTION (MAXRECURSION 0);

Which generates the following output.

Now to make it more fun, using the CSV conversion from a previous blog post, how do we convert it to a Comma Separated List.

WITH Fibonacci (PrevN, N) AS( SELECT 0, 1

UNION ALL

SELECT N, PrevN + N

FROM Fibonacci

WHERE N < 1000000000

)

SELECT Substring((SELECT cast(‘, ‘ as varchar(max)) + cast(PrevN as varchar(max))

FROM Fibonacci

FOR XML PATH(”)),3,10000000) AS list

Output…

What other classic math problems can you do with SQL Server.

More from Stedman Solutions:

Steve and the team at Stedman Solutions are here for all your SQL Server needs.
Contact us today for your free 30 minute consultation..
We are ready to help!