Fibonacci

Leonardo Fibonacci was born in 1170 AD. He was an Italian mathematican.

Fibonacci Sequence

0, 1, 1, 2, 3, 5, 8, 13, 21...

What is Fibonacci Sequence?

1. first two numbers are 0 and 1
2. each next element is a sum of two previous elements

Fibonacci(n) is equal to n-th element in Fibonacci Sequence

F(0)=0, F(1), F(2), F(3), ...

F(0), F(1), F(0) + F(1), F(1) + F(2), ...

0, 1, 1, 2, ...

Code in Scala

//Fibonacci01.main(Array())
object Fibonacci01 extends App {

  def fib(a : Int) : Int = {
    if (a == 0) 0 else 
    if (a == 1) 1 else 
    return fib(a - 1) + fib(a - 2)
  }
  
  println(fib(35))
}

Code result

()

Console output (click)

9227465

Execution time: 712 ms

Match/Case

//Fibonacci02.main(Array())
object Fibonacci02 extends App {

  /**
   * using match/case
   */
  def fib(a : Int) : Int = {
    a match {
      case 0 => 0
      case 1 => 1
      case n => fib(n - 1) + fib(n - 2)
    }
  }
  
  println(fib(35)) 
  // but fib(-1) will throw java.lang.StackOverflowError 
}

Code result

()

Console output (click)

9227465

Execution time: 695 ms Calling fib(-1) causes infinite loop.
Function Fibonacci is not defined for n < 0.

Match/Case using if

//Fibonacci03.main(Array())
object Fibonacci03 extends App {

  /**
   * function using match/case with if
   */
  def fib(a : Int) : Int = {
    a match {
      case 0 => 0
      case 1 => 1
      case n if (n > 1) => fib(n - 1) + fib(n - 2)
    }
  }
  
  println(fib(35))
  //fib(-1) throws scala.MatchError: 
}

Code result

()

Console output (click)

9227465

Execution time: 593 ms
Ok, nice, calling fib(-1) now causes MatchError
since is not covered by any case.

Let's create sequence - naive approach

//Fibonacci04.main(Array())
object Fibonacci04 extends App {

  /**
   * function using match/case with if
   */
  def fib(a : Int) : Int = {
    a match {
      case 0 => 0
      case 1 => 1
      case n if (n > 1) => fib(n - 1) + fib(n - 2)
    }
  }
  
  val numbers  = 0 to 35 //for each number
  val sequence : Seq = numbers.map(fib)  //apply function fib
  
  println(sequence)  //Vector(0, 1, 1, 2, 3, 5, 8, 13, 21)
}

Code result

()

Console output (click)

Vector(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465)

Execution time: 1042 ms
Much faster - Streaming and scanLeft

//Fibonacci05.main(Array())
object Fibonacci05 extends App {

  def fib : Stream = 0 #:: fib.scanLeft(BigInt(1))(_ + _)
  
  val sequence : Seq = fib.take(36)
  println(sequence.last)
  
}

Code result

()

Console output (click)

9227465

Execution time: 561 ms