Tail Recursive Fibonacci

Question

Please critique my implementation of a tail-recursive method for generating the Fibonacci sequence:

def fib(n: Int): Option[Int] = {
 @tailrec
 def go(count: Int, prev: Int, acc: Int): Option[Int] = {
 if (count == n) Some( acc )
 else go(count+1, acc, acc + prev)
 }
 if ( n < 0) None
 else if ( n == 0 ) Some( 0 )
 else if ( n == 1) Some ( 1 )
 else go(2, 1, 1)
}

• 200_success: Did you have any particular design goals while reinventing-the-wheel? There are alternative solutions, such as a lazy stream.

Answer 1

go is under your control, you can guarantee that it will always have a result, so you don't need to use Option for it. Also, the special cases for 0 and 1 are not neccessary. Counting backwards instead of forwards is more a matter of taste here, but it does reduce the dependency on the outer context.

def fib(n: Int): Option[Int] = {
 @tailrec
 def go(count: Int, prev: Int, acc: Int): Int = {
 if (count == 0) acc else go(count-1, acc, acc + prev)
 }
 if ( n < 0) None else Some(go(n, 1, 0))
}

However, if you want a really fast implementation (only interesting when you use BigInt), you should use these formulas, where you need only ~log(n) iterations instead of n:

$$ \begin{align} F_{2n-1} &= F_n^2 + F_{n-1}^2 \\ F_{2n} &= (F_{n-1} + F_{n+1}) F_n \\ &= (2F_{n-1} + F_n) F_n \end{align} $$

Answer 2

Option is not an appropriate type to return here. There is no doubt about whether a particular input can return a result or not; anything below zero will fail, anything above it will succeed. For once, failing hard is acceptable in the case of invalid input.

if...else if...else if...else chains are fragile and smelly in any language and really never necessary in Scala. Here, you are testing on precisely the same value each time. Use pattern matching.

 n match {
 case _ if n < 0 => ...
 case _ if n == 0 => ...
 case _ => ...
 }