-scala: naive Fibonacci

Fib.scala

def fib(i: Int): Int = i match {
  case 0 => 0
  case 1 => 1
  case x if x > 1 
         => fib(i - 1) + fib(i - 2)
  case _ => throw new IllegalArgumentException
}

Fix Fibonacci function using Option and Scalaz

import scalaz._, Scalaz._

def fib(i: Int): Option[Int] = i match {
  case 0 => 0.some
  case 1 => 1.some
  case x if x > 1 
         => fib(i - 1) >>= { a => fib(i - 2) >>= { b => (a + b).some } }
  case _ => None
}

Via For-Comprehension

def fib(i: Int): Option[Int] = i match {
  case 0 => 0.some
  case 1 => 1.some
  case x if x > 1
         => for { a <- fib(i - 1); b <- fib(i - 2) } yield a + b
  case _ => None
}

println(fib(-1)) // would return None
println(fib(10)) // would return Some(55)

Optimized version

import scalaz._, Scalaz._

def fib(n: Int) = {
  var xs = Array[BigInt](0, 1)
  var idx = 1
  for (i <- BigInt(2) to n) {
    xs = xs :+ i
    idx += 1
    xs(idx) = xs(idx - 1) + xs(idx - 2)
  }
  xs.last
}

fib(15).print