Fibonacci numbers in F#
- by BobPalmer
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!
