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