Skip to content

Instantly share code, notes, and snippets.

@CliffordAnderson
Last active December 31, 2015 14:08
Show Gist options
  • Save CliffordAnderson/7997843 to your computer and use it in GitHub Desktop.
Save CliffordAnderson/7997843 to your computer and use it in GitHub Desktop.
Fibonacci sequence in XQuery
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)
@CliffordAnderson
Copy link
Author

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.

@CliffordAnderson
Copy link
Author

To get a Fibonacci number, just get the final number in the sequence, e.g.

local:fibo-sequence(15)[fn:last()]

@CliffordAnderson
Copy link
Author

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()] 

@CliffordAnderson
Copy link
Author

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.

@CliffordAnderson
Copy link
Author

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)

@CliffordAnderson
Copy link
Author

See this XQuery Wikibook for more information about the Fibonacci algorithm in XQuery as well as how to time the difference between implementations.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment