HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

Fibonacci number function: convert to tail-recursion?

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
numberfibonaccirecursionconvertfunctiontail

Problem

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?

Solution

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

Code Snippets

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

Context

StackExchange Code Review Q#56209, answer score: 3

Revisions (0)

No revisions yet.