Friday 16 August 2013

Fibonacci in Scala: so many ways

Version 1, classic, pattern matching:
  def fibonacci_1(n: Int): Int = n match {
    case n if n <= 0 => 0
    case 1 => 1
    case _ => fibonacci_1(n - 1) + fibonacci_1(n - 2)
  }                                           
Version 2, using fold:
  def fibonacci_2(n: Int):Int = (((0, 1) /: (1 to n)) ((a, dummy) => (a._2, a._1 + a._2)))._1
Version 3, using streams:
  lazy val fibonacci_3: Stream[BigInt] = 0 #:: 1 #:: (fibonacci_3 zip fibonacci_3.tail map {case (x, y) => x + y})
Version 4, same as 1, but tail recursive:
  def fibonacci_tail_rec(n: Int, b: Int, a: Int): Int = n match {
    case 0 => a
    case _ => fibonacci_tail_rec(n - 1, a + b, b)
  }  
  def fibonacci_4(n: Int): Int = fibonacci_tail_rec(n, 1, 0)
Let's double check that they yield the same results:
  fibonacci_1(19)             //> res0: Int = 4181
  fibonacci_2(19)             //> res1: Int = 4181
  (fibonacci_3 take 20).last  //> res2: BigInt = 4181
  fibonacci_4(19)             //> res3: Int = 4181

No comments:

Blog Archive