Fibonacci sequence in XQuery

fibonacci.xqy

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)

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.