Scala: Hello Fibonacci

by Michael

Let’s start with some easy Scala coding, like generating the Fibonacci sequence. A nice problem because it uses recursion and we can expand upon the solution by creating a memoizer to save the intermediate results for when we need them again.

Fibonacci sequence: 1, 1, 2, 3, 5, … , f(n) = f(n-2) + f(n-1)

This gives us the following first 3 terms

  1. f(0) = 1
  2. f(1) = 1
  3. f(2) = 2

The third term can be written in the following way

f(2) = f(0) + f(1) = 1 + 1 = 2

Using the same premise, we can write the fourth term as

f(3) = f(1) + f(2)
f(3) = f(1) + (f(0) + f(1)) = 1 + 1 + 1 = 3

So the base terms are f(0) = 1 and f(1) = 1 and the recursive term is f(n) = f(n-2) + f(n-1). In Scala, this is

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

To run this as a stand alone program, write

object FibApp {

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

  def main(args: Array[String]) {
    println(fib(30))
  }
}

You’ll notice that the results for n < 40 take a “reasonable” time to compute, whereas results for n > 40 take a long time or even result in a stack overflow. We can use memoization to store the result of the previous calculations, this should decrease the amount of time required for generating results for larger values of n.

Advertisements