If you're interested in functional programming, you might also want to checkout my second blog which i'm actively working on!!

Wednesday, November 25, 2009

Fibonnaci in scala

The first implementation below is my own implementation which stores all calculated values
directly in the array and reuses those values to calculate following values.


Another implementation which heavily uses recursion is implemented using pattern matching. See wikipedia. But as you would expect this implementation has bad performance as we will prove. But nevertheless pattern matching opens up a lot of possibilities.




results in

fibonnaci processed 30 numbers in 16 miliseconds.
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229
fibonnaci2 processed 30 numbers in 47 miliseconds.
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229


In fact the first implementation can print 1000 numbers in almost the same amount of time.... The 2nd implementation however will become unresponsive from n > 50...

Lesson learned: Be carefull in how you use recursion.

No comments:

Post a Comment