I've been implementing a function for calculating the nth Fibonacci number in F#. So far the best implementation I could come up with is this:
let fib n = let rec fib = function | 0 -> 0I, 1I | n -> let f1, f2 = fib (n / 2) let f1' = f1 * (2I * f2 - f1) let f2' = f2 * f2 + f1 * f1 if n % 2 = 0 then (f1', f2') else (f2', f1' + f2') fib n |> fst
Can it be improved or written in a more F#-idiomatic way?
Also, as a separate question, can it be rewritten to be tail-recursive?