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 n2 c =

    if c = 1 then

        n2

    else

        fib n2 (n1+n2) (c-1);;

let GetFib num =

    (fib 1 1 num);;

printfn "%A" (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.

 

Enjoy!