Generating the Fibonacci Sequence in Scala

1. Introduction

The Fibonacci sequence consists of positive numbers, with each element being the sum of the two preceding numbers. The first two elements of the sequence are 0 and 1.

In this tutorial, we’ll explore various methods for creating the Fibonacci sequence in Scala.

2. Using Recursion

We can easily generate the sequence using recursion:

def fibSequenceRecursion(sequenceSize: Int): Seq[Long] = {
  def getNextNum(num: Long): Long = {
    if (num <= 1) {
      num
    } else {
      getNextNum(num - 1) + getNextNum(num - 2)
    }
  }
  (0L until sequenceSize).map(getNextNum)
}

In the above implementation, we calculate the nth element of the Fibonacci sequence by recursively summing the value of (n-1)th and (n-2)th elements. This implementation is straightforward to implement and understand. However, it lacks efficiency. During the calculation of each element, the code redundantly recomputes the entire preceding sequence.

3. Using Tail Recursion

We can rewrite the previous recursive implementation into a tail recursive solution:

def fibTailRec(sequenceSize: Int): Seq[Long] = {
  @tailrec
  def fib(n: Int, a: Long, b: Long, acc: List[Long]): List[Long] = {
    if (n <= 0) acc
    else fib(n - 1, b, a + b, acc :+ a)
  }
  fib(sequenceSize, 0L, 1, Nil)
}

In the above implementation, the fib() function is a tail-recursive function responsible for computing the next element in the sequence. Unlike the previous implementation, this solution supplies the recursive function with the preceding two elements of the sequence as parameters. Consequently, it avoids the need to recalculate the entire sequence when determining the next element, thus improving efficiency.

4. Using Iterator

Another way to generate the Fibonacci sequence is by using Iterator. Iterator allows us to process the elements lazily. We can utilize the iterate() method on Iterator to calculate the next element of the sequence.

Let’s look at the implementation:

def fibIterator(sequenceSize: Int): List[Long] = {
  Iterator
    .iterate((0L, 1L)) { case (a, b) => (b, a + b) }
    .map(_._1)
    .take(sequenceSize)
    .toList
}

The iterate() method takes the starting value for the iterator as the first parameter. In this case, we use a tuple (0,1) as the starting value of the iterator representing the first two elements of the Fibonacci sequence. Meanwhile, the second parameter of the iterate() method accepts a code block responsible for generating the subsequent element based on the current value.

By summing the tuple elements and creating a new tuple with the updated and previous values, the next element is seamlessly generated. Subsequently, we can extract the first element of each tuple to generate the sequence. This solution is particularly efficient because it avoids the requirement to recalculate earlier elements, as they are available within the tuple.

5. Using LazyList

Yet another efficient way to generate the Fibonacci sequence is by using LazyList. LazyList is a collection type that evaluates its element lazily and only on demand. As a result, we can make use of LazyList to handle potentially infinite sequences. 

Let’s implement the Fibonacci sequence using LazyList:

def fibLazyList(sequenceSize: Int): Seq[Long] = {
  lazy val fib: LazyList[Long] = 0L #:: 1L #:: fib.zip(fib.tail).map(_ + _)
  fib.take(sequenceSize).toList
}

In this instance, we define a LazyList using a recursive syntax. Zero and One are the initial two elements of the LazyList.

Subsequently, we calculate the next element of the sequence by summing the previous two elements using the zip method applied to its tail. The newly calculated element is added to the LazyList and the same can be used for the calculation of the next element.

The sequence is calculated on demand, and only the necessary elements are computed. Consequently, this approach is memory-efficient and can handle sequences of potentially infinite length.

6. Conclusion

In this article, we looked at different ways to generate the Fibonacci sequence.

Even though the simple recursion method is the easiest to understand, its performance is not adequate. We may be able to improve its performance using additional caching layers to avoid the recalculation. However, we learned that Scala provides more idiomatic and efficient ways to implement a solution.

As always, the sample code used in this article is available over on GitHub.