Tail Recursive Fibonacci 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 &lt; 0)   None
    else if ( n == 0 ) Some( 0 )
    else if ( n == 1)  Some ( 1 )
    else               go(2, 1, 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 &lt; 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} &amp;= F_n^2 + F_{n-1}^2 \\
F_{2n}   &amp;= (F_{n-1} + F_{n+1}) F_n \\
         &amp;= (2F_{n-1} + F_n) F_n
\end{align}
$$