4
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Jamal Jul 5 '14 at 17:12
  • 2
    \$\begingroup\$ @Jamal, I thought converting to tail-recursion can count as improvement? \$\endgroup\$ – Regent Jul 5 '14 at 17:17
  • \$\begingroup\$ Only if it's already here in some form. \$\endgroup\$ – Jamal Jul 5 '14 at 17:18
  • \$\begingroup\$ I don't like that the two functions have exactly the same name. Otherwise, this seems like a good way to write this. \$\endgroup\$ – svick Jul 7 '14 at 18:09
2
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.