snippetMinor
Fibonacci number function: convert to tail-recursion?
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:
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?
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 |> fstCan 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 nCode Snippets
let fib n =
let rec tail n1 n2 = function
| 0 -> n1
| n -> tail n2 (n2 + n1) (n - 1)
tail 0I 1I nContext
StackExchange Code Review Q#56209, answer score: 3
Revisions (0)
No revisions yet.