As you may have gathered from some of my previous posts, I've been spending some quality time at
Project Euler. Normally I do my solutions in C#, but since I have also started learning F#, it only made sense to switch over to F# to get my math coding fix.
This week's post is just a small snippet - spefically, a simple function to return a
fibonacci number given it's place in the sequence. One popular example uses recursion:
let rec fib n = if n < 2 then 1 else fib (n-2) + fib(n-1)
While this is certainly elegant, the recursion is absolutely brutal on performance. So I decided to spend a little time, and find an option that achieved the same functionality, but used a recursive function. And since this is F#, I wanted to make sure I did it without the use of any mutable variables.
Here's the solution I came up with:
let rec fib (n1 : bigint) (n2 : bigint) c =
if c = 1 then
n2
else
fib n2 (n1+n2) (c-1);;
let GetFib num =
(fib 1I 1I num);;
printfn "%O" (GetFib 1000);;
Essentially, this function works through the sequence moving forward, passing the two most recent numbers and a counter to the recursive calls until it has achieved the desired number of iterations. At that point, it returns the latest fibonacci number.
(Edited to change from Int to BigInt - Thanks for the feedback!)
Enjoy!