5
\$\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\$
4
  • \$\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
    Commented Jul 5, 2014 at 17:12
  • 2
    \$\begingroup\$ @Jamal, I thought converting to tail-recursion can count as improvement? \$\endgroup\$
    – Regent
    Commented Jul 5, 2014 at 17:17
  • \$\begingroup\$ Only if it's already here in some form. \$\endgroup\$
    – Jamal
    Commented Jul 5, 2014 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
    Commented Jul 7, 2014 at 18:09

1 Answer 1

3
\$\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 and acknowledge you have read our privacy policy.

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