-
-
Save CliffordAnderson/7997843 to your computer and use it in GitHub Desktop.
xquery version "3.0"; | |
(: Fibonacci Sequence :) | |
declare function local:fibo-numbers($num1 as xs:integer, $num2 as xs:integer, $limit as xs:integer) as xs:integer* { | |
if ($limit > 0) then ($num1, local:fibo-numbers($num2, $num1 + $num2, $limit -1)) | |
else $num1 | |
}; | |
declare function local:fibo-sequence($limit as xs:integer) as xs:integer* { | |
local:fibo-numbers(0, 1, $limit) | |
}; | |
local:fibo-sequence(15) |
To get a Fibonacci number, just get the final number in the sequence, e.g.
local:fibo-sequence(15)[fn:last()]
Just as a reminder, dividing a Fibonacci number by its predecessor produces an approximation of the Golden Ratio (1.61803398875).
local:fibo-sequence(199)[fn:last()] div local:fibo-sequence(198)[fn:last()]
A classically recursive algorithm for computing Fibonacci numbers is even simpler:
xquery version "3.0";
declare function local:fibo($num as xs:integer) as xs:integer {
if ($num = 0) then 0
else if ($num = 1) then 1
else (local:fibo($num - 1) + local:fibo($num - 2))
};
local:fibo(20)
However, the depth of the recursion required for calculating numbers above twenty-five slows down the computation dramatically.
A tail-recursive version is blazingly fast because it does not need to keep intermediate values on the stack. Notice how close this tail-recursive version is to the initial algorithm for generating the sequence above:
(: Fibonacci Number :)
declare function local:fibo-sequence($num1 as xs:integer, $num2 as xs:integer, $limit as xs:integer) as xs:integer* {
if ($limit > 0) then local:fibo-sequence($num2, $num1 + $num2, $limit -1)
else $num1
};
declare function local:fibo-number($limit as xs:integer) as xs:integer* {
local:fibo-sequence(0, 1, $limit)
};
local:fibo-number(200)
See this XQuery Wikibook for more information about the Fibonacci algorithm in XQuery as well as how to time the difference between implementations.
I'm reading Stephen Ramsey's discussion of the Fibonacci sequence in Reading Machines: Toward an Algorithmic Criticism and figured that I'd better write an XQuery version of the algorithm.