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?

By definition, the first two numbers in the Fibonacci sequence are 0 and 1, and each subsequent number is the sum of the previous two.

For instance, the following are Fibonacci Numbers:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733 …

 

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.

2 Responses to Fibonacci Sequence

  1. Pingback: » SQL Lunch UK Steve Stedman

  2. Pingback: » Temp Table vs Table Variable vs CTE and the use of TEMPDB. Steve Stedman

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Powered by sweetCaptchaWordpress Captcha