Enrico Susatyo Enrico Susatyo - 2 months ago 12
Scala Question

What is the fastest way to write Fibonacci function in Scala?

I've looked over a few implementations of Fibonacci function in Scala starting from a very simple one, to the more complicated ones.

I'm not entirely sure which one is the fastest. I'm leaning towards the impression that the ones that uses memoization is faster, however I wonder why Scala doesn't have a native memoization.

Can anyone enlighten me toward the best and fastest (and cleanest) way to write a fibonacci function?

Answer

for me the simplest defines a recursive inner tail function:

def fib: Stream[Long] = {
  def tail(h: Long, n: Long): Stream[Long] = h #:: tail(n, h + n)
  tail(0, 1)
}

This doesn't need to build any Tuple objects for the zip and is easy to understand syntactically.