Fibonacci number function: convert to tail-recursion?

Question

I've been implementing a function for calculating the n^th 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?

• Jamal: The question regarding tail-recursion is off-topic as we do not assist in adding additional implementation. As long as everything else works, it can still be reviewed.
• Regent: @Jamal, I thought converting to tail-recursion can count as improvement?
• Jamal: Only if it's already here in some form.
• svick: I don't like that the two functions have exactly the same name. Otherwise, this seems like a good way to write this.

Answer 1

A concise and idiomatic (I think) implementation (which happens to be tail recursive) but without your / 2 optimisation would be:

let fib n =
 let rec tail n1 n2 = function
 | 0 -> n1
 | n -> tail n2 (n2 + n1) (n - 1)
 tail 0I 1I n