5 ways to solve Fibonacci in Scala – Tail Recursion, Memoization, The Pisano Period & More

One of the classic problems in order to explain Recursion in Computer Science is the typical Fibonacci Sequence, which takes its name in honor to Leonardo De Pisa, the Italian Mathematician who wrote the Liber Abaci in order to convince the public about the superiority of the Hindu-Arabic numeral system.

The Fibonacci Sequence is characterized by the fact that every number in it is equal to the sum of the preceding ones:

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

The formal definition of the sequence Fn of Fibonacci numbers is:

Fn = Fn-1 + Fn-2

Where F0 = 0 and F1 = 1

We can solve this classical problem in Scala using 5 different approaches with their own advantages and disadvantages depending on how large is the Fibonacci sequence needed to get our solution.

 

Case 1: Pattern Matching
– Well suited for small numbers
– If n is big, throws Stack Overflow
– Gets really slow for n > 40 approx.

 

def fib1(n: Int): Int = n match {
   case 0 | 1 => n
   case _ => fib1(n – 1) + fib1(n – 2)
}

 

Case 2: Loop
– Handles Integer numbers (32 bit)
– Too verbose, non-idiomatic, mutable variables.

 

def fib2(n: Int): Int = {

   var first = 0
   var second = 1
   var count = 0

   while(count < n){
      val sum = first + second
      first = second
      second = sum
      count = count + 1
   }

   return first
}

 

Case 3: Tail Recursion
– Optimized by compiler

 

def fib3(n: Int): Int = {
   def fib_tail(n: Int, a: Int, b: Int): Int = n match {
      case 0 => a
      case _ => fib_tail(n – 1, b, a + b)
   }
   return fib_tail(n, 0 , 1)
}

 

Case 4: Memoization
– Optimization by Caching.
– Not suitable for big amounts.

(Substitute 185 with the amount of numbers to print)

val fib: Stream[BigInt] = 0 #:: 1 #:: fib.zip(fib.tail).map(p => p._1 + p._2)

def main(args: Array[String]){
   val s = fib take 185 mkString ” “
   print(s)
   println()
   print(fib(180))
}

 

Extra Case: The Pisano Period
– Gets the last n digits of Fibonacci with tail recursion (6 for this example)

def fib5( n : Int) : Int = {
   def fib_tail( n: Int, a:Int, b:Int): Int = n match {
      case 0 => a
      case _ => fib_tail( n-1, b, (a+b)%1000000 )
   }
   return fib_tail( n%1500000, 0, 1)
}

 

Grab the code at: Github

Advertisements