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:
Post a Comment