### 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

*f(0) = 1**f(1) = 1**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*.