Fibonacci Sequence CTE

Question

Fibonacci Sequence CTE

Mordred

SSCrazy

Points: 2904
More actions
October 9, 2010 at 4:55 pm

#230220

Hi all,
I am a student who is relatively new to SQL. While I am not looking for someone to do my work for me, I was hoping for some pointers. I have the following CTE code which attempts to find the 10th Fibonacci number:
WITH Fib(Num, fib, fib2) AS (SELECT 1 AS Expr1, 0 AS Expr2, 1 AS Expr3
UNION ALL
SELECT Num + 1 AS Expr1, fib + fib2 AS Expr2, fib
FROM Fib AS fib_2
WHERE (Num <= 10))
SELECT Num, fib AS Fibonacci_Number
FROM Fib AS Fib_1
WHERE (Num = 10)
The problem is the debate on whether or not 0 is used as the first sequence number. The previous code outputs 34 as the tenth, which some agree with (according to a Google search). However, some think the 10th Fibonacci number is 55. My question is, if 55 is considered to be the 10th number, how would I incorporate that into my code?
Regards:
Mordred
Keep on Coding in the Free World

Viewing 7 posts - 1 through 6 (of 6 total)

You must be logged in to reply to this topic. Login to reply

Jeff Moden SSC Guru Points: 1003875 More actions · Answer 1

IIRC, by definition, the first Fibonacci number is refererred to as F₀ = 0 and F₁ = 1 soooooo the TENTH number is actually F₉ = 34.

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

Mordred SSCrazy Points: 2904 More actions · Answer 2

Thanks for your response. I agree with that logic but then why are there so many that would say 55 is the tenth I wonder?

Regards:
Mordred
Keep on Coding in the Free World

Jeff Moden SSC Guru Points: 1003875 More actions · Answer 3

Mordred (10/9/2010)
Thanks for your response. I agree with that logic but then why are there so many that would say 55 is the tenth I wonder?

Mostly because they start counting from "0" and count 0,1,2,3,4,5,6,7,8,9,10. 10 in this case, is the 11th number and so is the 55. I guess "It Depends" ... can you call the first number the "zeroth" number"??? I doubt it but you never know.

Ask them if they count from 0 to 9 if the 9 is the 9th number or the tenth number in the series.

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

Mordred SSCrazy Points: 2904 More actions · Answer 4

Thanks again. Personally, when I count to 9 I'll start at 1 not 0. However, when it comes to programming, 0 is used as the first number in the sequence so therefore the sequence will always start at 0 (please correct me if I'm wrong). Anyhow, I just received an email from my prof on this matter and he said it didn't matter if the outcome was either 34 or 55. I was wondering though, if I wanted the tenth number f(10) to be 55, what change to the code would be needed? I've been playing with it but have not found a way to do this.

Regards:
Mordred
Keep on Coding in the Free World

TomThomson SSC Guru Points: 104773 More actions · Answer 5

Mordred (10/9/2010)
Thanks again. Personally, when I count to 9 I'll start at 1 not 0. However, when it comes to programming, 0 is used as the first number in the sequence so therefore the sequence will always start at 0 (please correct me if I'm wrong). Anyhow, I just received an email from my prof on this matter and he said it didn't matter if the outcome was either 34 or 55. I was wondering though, if I wanted the tenth number f(10) to be 55, what change to the code would be needed? I've been playing with it but have not found a way to do this.

It looks as if it should work if you just change the first line of your code to be

WITH Fib(Num, fib, fib2) AS (SELECT 1 AS Expr1, 1 AS Expr2, 1 AS Expr3, so that the first number you count is 1 instead of 0.

Tom

WayneS SSC Guru Points: 95409 More actions · Answer 6

Mordred (10/9/2010)
Hi all,
I am a student who is relatively new to SQL. While I am not looking for someone to do my work for me, I was hoping for some pointers. I have the following CTE code which attempts to find the 10th Fibonacci number:
WITH Fib(Num, fib, fib2) AS (SELECT 1 AS Expr1, 0 AS Expr2, 1 AS Expr3
UNION ALL
SELECT Num + 1 AS Expr1, fib + fib2 AS Expr2, fib
FROM Fib AS fib_2
WHERE (Num <= 10))
SELECT Num, fib AS Fibonacci_Number
FROM Fib AS Fib_1
WHERE (Num = 10)
The problem is the debate on whether or not 0 is used as the first sequence number. The previous code outputs 34 as the tenth, which some agree with (according to a Google search). However, some think the 10th Fibonacci number is 55. My question is, if 55 is considered to be the 10th number, how would I incorporate that into my code?

Change WITH Fib(Num, fib, fib2) AS (SELECT 1 AS Expr1, 0 AS Expr2, 1 AS Expr3

to WITH Fib(Num, fib, fib2) AS (SELECT 0 AS Expr1, 0 AS Expr2, 1 AS Expr3

(Change the where to (Num <=10) to see the whole chain.)

Wayne
Microsoft Certified Master: SQL Server 2008
Author - SQL Server T-SQL Recipes

If you can't explain to another person how the code that you're copying from the internet works, then DON'T USE IT on a production system! After all, you will be the one supporting it!

Links:
For better assistance in answering your questions
Performance Problems
Common date/time routines
Understanding and Using APPLY Part 1 & Part 2