Fibonacci Numbers in Scala
Working out the Fibonacci numbers are a standard exercise when learning a programming language, or just refreshing your knowledge. Below, is a recap of various ways to calculate them in Scala. All the code is available in a handy gist.
First, a quick recap of the beginning of the series. If this is unfamiliar to you, please click the first link in this post!
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
Nth Fibonacci Number
Given a number n, return the corresponding Fibonacci number from the sequence.
Lets start off really basically, and use a while loop.
The first thing to notice about the Fibonacci sequence is that the first two numbers match their indexes. The 0th number is 0, and the 1st number is 1. These form the foundation of later calculations, and is the reason for the if-statement on line 2 of the code snippet.
We can do better though. Fibonacci sequences rely on previous calculations, so are an ideal opportunity to use recursion:
This looks good! Basically only two lines of code, and its fairly easy to follow. However, the keen-eyed amongst you may note that for large values of n, a
StackOverflowException may be thrown! To prevent these exceptions when writing recursive code, it is encouraged that we write in a tail-recursive form. The compiler will attempt to optimise the recursion.
Also note that for large n’s, we need to use
BigInt to avoid integer overflow.
Fibonacci Series, of length n
Given a number n, return the fibonacci series of length n.
This time, instead of returning one number, we want a whole series. Well, we already have a function that returns the nth Fibonacci number, lets just use that!
Whilst we should really benchmark this, to see exactly how terrible it is, we will assume that is too inefficient; it forgets all previous calculations when trying to work out the next number.
How else can we do this then? We can use an accumulator:
This has a nasty list creation to append the number onto the end of the list. We have to pass around
i everywhere. Scala’s
List is a Linked List. Appending is hard, but prepending is easy. This is what the cons operator is for! By constructing the list in reverse we can optimise for a linked list, and remove the
Marvellous. It does get better though. For those of you familiar with
Stream, you can do this:
#:: operator prepends an element to the start of the Stream, and
scanLeft works just like
foldLeft but returns a Stream. The Scaladoc for Stream actually contains a different version of how to calculate a Fibonacci sequence, but I prefer to use
scanLeft for its terseness, and the analogy with