Recursive Fibonacci number calculation
The answer to your question is "Yes, I am having a slow day today."
;WITH Fibonacci(n, f, f1)
AS (
SELECT CAST(1 AS BIGINT),
CAST(0 AS BIGINT),
CAST(1 AS BIGINT)
UNION ALL
SELECT n + 1,
f + f1,
f
FROM Fibonacci
WHERE n < 93
)
SELECT n,
f AS Number
FROM Fibonacci
Legacy Comments
|
Liam Caffrey
2009-08-27 |
re: Recursive Fibonacci number calculation Hi, I am trying to understand how this is working... -- Iteration 1 SELECT CAST(1 AS BIGINT) as n ,CAST(0 AS BIGINT) as f ,CAST(1 AS BIGINT) as f1 UNION ALL -- Iteration 2 SELECT 1 + 1 ,0 + 1 ,0 union all -- Iteration 3 SELECT 2 + 1 ,1 + 0 ,1 union all -- Iteration 4 SELECT 3 + 1 ,1 + 1 ,1 union all -- Iteration 5 SELECT 4 + 1 ,2 + 1 ,2 union all -- Iteration 6 SELECT 5 + 1 ,3 + 2 ,3 union all -- Iteration 7 SELECT 6 + 1 ,5 + 3 ,5 union all -- Iteration 8 SELECT 7 + 1 ,8 + 5 ,8 What I cannot figure out is why it only pulls the last member from the previous level each time it recurses. I kind of expected it to be pulling the accumulated recursive members out each time getting something like. -- Iteration 1 SELECT CAST(1 AS BIGINT) as n ,CAST(0 AS BIGINT) as f ,CAST(1 AS BIGINT) as f1 UNION ALL -- Iteration 2 SELECT 1 + 1 ,0 + 1 ,0 union all -- Iteration 3 SELECT 2 + 1 ,1 + 0 ,1 union all ( SELECT CAST(1 AS BIGINT) as n ,CAST(0 AS BIGINT) as f ,CAST(1 AS BIGINT) as f1 UNION ALL -- Iteration 2 SELECT 1 + 1 ,0 + 1 ,0 ) etc.. It must be only pulling the last level each recursion. Normally the recursive member is joined to the anchor member but there is no join here. Any ideas? |
|
Peso
2009-08-27 |
re: Recursive Fibonacci number calculation I am doing two columns at the same time, so I shift the number vertical, not horizontal. |
|
Scott R.
2009-08-27 |
re: Recursive Fibonacci number calculation Peter, Thanks for providing this great learning example of a recursive query using CTEs. Building on your example, I wondered if SQL Server was capable of going higher than 92 in the Fibonacci series. So I changed the BIGINT data types to DECIMAL(38,0), reran it with a larger upper limit of 200, and got the following error message: Msg 530, Level 16, State 1, Line 1 The statement terminated. The maximum recursion 100 has been exhausted before statement completion. There is a server-level recursion limit, which defaults to 100. If I set the query upper limit to 100, the query would work fine (no errors). The server-level recursion limit can be changed, but I didn’t want to do that unless no other options were available. I then discovered the query statement level MAXRECURSION option, changed it to 200, and played with gradually increasing upper limits until the capacity of the DECIMAL(38,0) data type was exceeded at 184. So the new upper limit is 183, versus 92 with the BIGINT data type. I also added a third column to the displayed query results that shows how many decimal digits are in the Fibonacci series number, so you can observe them gradually grow larger. With the exception of single-digit results at the start of the series, an extra digit is added in the result every 4 to 5 iterations in the series. This is about right when you consider that the next result in the series is slightly less than approximately double the previous result, and log base 2 of 10 is about 3.32. The ratio between current and previous Fibonacci values seems to converge at 1.618. I added a fourth column to the displayed query results to show this ratio at each point in the series. Incidentally, Log(10) / Log(1.618) = about 4.785 – confirming the 4 and 5 series iterations per digit growth in the series result. The revised query follows: ;WITH Fibonacci(n, f, f1) AS ( SELECT CAST(1 AS DECIMAL(38, 0)), CAST(0 AS DECIMAL(38, 0)), CAST(1 AS DECIMAL(38, 0)) UNION ALL SELECT n + 1, f + f1, f FROM Fibonacci WHERE n < 184 ) SELECT n, f AS Number, LEN(CAST(f AS VARCHAR(100))) AS '# Digits', CASE WHEN (f1 > 0) THEN CAST(f AS FLOAT) / CAST(f1 AS FLOAT) ELSE 0 END AS Ratio FROM Fibonacci OPTION (MAXRECURSION 200); Thanks again for inspiring this experiment. Slow days can be fun! Scott R. |
|
Liam Caffrey
2009-08-28 |
re: Recursive Fibonacci number calculation Scott, The ratio is in fact the Golden Ratio. http://en.wikipedia.org/wiki/Golden_ratio#Relationship_to_Fibonacci_sequence Also, I think that I figured out what is going on here. There is no recursion in the hierarchical sense which is what was confusing me, merely the cte_name is being used to generate new n, f and f1 values in the same way as a procedural function would, the only constraint being n < 93. Interestingly, the level doesn't change. The fact that there is only 1 record in the anchor set means that each "recursion" multiplies the previous cross-product by 1. The following link was helpful. http://msdn.microsoft.com/en-us/library/ms186243.aspx You can see that by changing the union statement in the anchor set of the cte affects the way the statement runs WITH Fibonacci(n, f, f1, level) AS ( select a.* from ( SELECT CAST(1 AS DECIMAL(38, 0)) as n ,CAST(0 AS DECIMAL(38, 0)) as f ,CAST(1 AS DECIMAL(38, 0)) as f1 ,0 as level --union all union SELECT CAST(1 AS DECIMAL(38, 0)) as n ,CAST(0 AS DECIMAL(38, 0)) as f ,CAST(1 AS DECIMAL(38, 0)) as f1 ,0 as level ) a UNION ALL SELECT n + 1 ,f + f1 ,f ,level FROM Fibonacci a WHERE n < 8 ) SELECT n ,f AS Number ,LEN(CAST(f AS VARCHAR(100))) AS '# Digits' ,CASE WHEN (f1 > 0) THEN CAST(f AS FLOAT) / CAST(f1 AS FLOAT) ELSE 0 END AS Ratio ,level FROM Fibonacci OPTION (MAXRECURSION 20000); Thanks, Liam |
|
Charlie
2009-09-01 |
re: Recursive Fibonacci number calculation I posted a way to get an (almost) arbitrarily large number of fibs. Here. Old school Character arithmetic - brings back memories of those old 8 bit days.... http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=130689 |