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
– Simple and well suited for small numbers, but it doesn’t scale
– If n is big, we run the risk of getting a Stack Overflow

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

 

Case 2: Loop
– Handles Long numbers (64 bit)
– A little bit too verbose, non-idiomatic, mutable variables.

def fib2(n: Long): Long = {
  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 the compiler. We say a function is tail recursive when the recursive call is the last thing executed by the function. In this example, we can see the fib_tail call being applied in the last line of code inside the fib3 function.

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: Lazy Evaluation with Scala Streams and Memoization

A Stream is similar to a list, with the exception that its elements are computed lazily, this means that a Stream can be infinitely long and only the elements requested at a given time will be computed. By combining this technique with the usage of  BigInt types, we obtain nothing less than a mortal weapon that we can use on sites like LeetCode and Hackerrank to completely obliterate Fibonacci-based problems and obtain massive performance improvements.

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

def fib4(n: Int) = fib(n)

Also, we can create a memoize wrapper in combination with the previously defined stream to keep a cache and make things even more performant.

def memoize[A, B](f: A => B): A => B =
  new collection.mutable.WeakHashMap[A, B] {
    override def apply(a: A) = getOrElseUpdate(a, f(a))
  }

val memofib = memoize(fib)

And then, we can call it using memofib(<number>), for example: memofib(100)

 

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

The nth Pisano Period, written π(n), is the period with which the sequence of Fibonacci numbers taken modulo n repeats. Pisano periods are named after Leonardo Pisano, better known as Fibonacci. This name was made up in 1838 by the Franco-Italian historian Guillaume Libri and is short for filius Bonacci (‘son of Bonacci’).

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

The Scala Ecosystem: Infographics

the scala ecosystem (6)

 

Frameworks

  • Play!: Play is an open source web application framework, written in Scala and Java, which follows the model–view–controller (MVC) architectural pattern. It aims to optimize developer productivity by using convention over configuration, hot code reloading and display of errors in the browser. www.playframework.com
  • Lift: Lift is an expressive framework for writing web applications. It draws upon concepts from peer frameworks such as Grails, Ruby on Rails, Seaside, Wicket and Django. It favors convention over configuration in the style of Ruby on Rails, although it does not prescribe the model–view–controller (MVC) architectural pattern. www.liftweb.net
  • Skinny: Skinny is a full-stack web app framework built on Skinny Micro. To put it simply, Skinny framework’s concept is Scala on Rails. Skinny is highly inspired by Ruby on Rails and it is optimized for sustainable productivity for Servlet-based web app development. http://skinny-framework.org/
  • Scalatra: Scalatra is a simple, accessible and free web micro-framework. It combines the power of the JVM with the beauty and brevity of Scala, helping you quickly build high-performance web sites and APIs. http://www.scalatra.org/
  • Spray: Spray is an open-source toolkit for building REST/HTTP-based integration layers on top of Scala and Akka. Being asynchronous, actor-based, fast, lightweight, modular and testable it’s a great way to connect your Scala applications to the world. http://spray.io/

Tools

  • Akka: Akka is an open-source toolkit and runtime simplifying the construction of concurrent and distributed applications on the JVM. Akka supports multiple programming models for concurrency, but it emphasizes actor-based concurrency, with inspiration drawn from Erlang. http://akka.io/
  • ScalikeJDBC: ScalikeJDBC is a tidy SQL-based DB access library for Scala developers. This library naturally wraps JDBC APIs and provides you easy-to-use and very flexible APIs. What’s more, QueryDSL makes your code type-safe and reusable. http://scalikejdbc.org/
  • ScalaJS: Scala.js is a compiler that compiles Scala source code to equivalent Javascript code. That lets you write Scala code that you can run in a web browser, or other environments (Chrome plugins, Node.js, etc.) where Javascript is supported. https://www.scala-js.org/
  • Slick: Slick is a modern database query and access library for Scala. It allows you to work with stored data almost as if you were using Scala collections while at the same time giving you full control over when a database access happens and which data is transferred.  http://slick.lightbend.com/
  • Kafka: is an open-source message broker project developed by the Apache Software Foundation written in Scala. The project aims to provide a unified, high-throughput, low-latency platform for handling real-time data feeds.  http://kafka.apache.org/

Testing

IDE’s

Live Events & Conferences

Job Websites

Useful Links & Resources