One of the most popular number series being used as a programming exercise is undoubtedly the Fibonacci numbers:
|
1 2 3 |
F(0) = 1 F(1) = 1 F(n) = F(n-1) + F(n-2) |
Perhaps a prominent reason why the Fibonacci sequence is of vast interest in Math is the associated Golden Ratio, but I think what makes it a great programming exercise is that despite a simplistic definition, the sequence’s exponential growth rate presents challenges in implementations with space/time efficiency in mind.
Having seen various ways of implementing methods for the Fibonacci numbers, I thought it might be worth putting them together, from a naive implementation to something more space/time efficient. But first, let’s take a quick look at the computational complexity of Fibonacci.
Fibonacci complexity
If we denote T(n) as the time required to compute F(n), by definition:
|
1 |
T(n) = T(n-1) + T(n-2) + K |
where K is the time taken by some simple arithmetic to arrive at F(n) from F(n-1) and F(n-2).
With some approximation Math analysis (see this post), it can be shown that the lower bound and upper bound of T(n) are O(2^(n/2)) and O(2^n), respectively. For better precision, one can derive a more exact time complexity by solving the associated characteristic equation, x^2 = x + 1, which yields x = ~1.618 to deduce that:
|
1 |
Time complexity for computing F(n) = O(R^n) |
where R = ~1.618 is the Golden Ratio.
As for space complexity, if one looks at the recursive tree for computing F(n), it’s pretty clear that its depth is F(n-1)’s tree depth plus one. Thus, the required space for F(n) is proportional to n. In other words:
|
1 |
Space complexity for computing F(n) = O(n) |
The relatively small space complexity compared with the exponential time complexity explains why computing a Fibonacci number too large for a computer would generally lead to an infinite run rather than a out-of-memory/stack overflow problem.
It’s worth noting, though, if F(n) is computed via conventional iterations (e.g. a while-loop or tail recursion which gets translated into iterations by Scala under the hood), the time complexity would be reduced to O(n) proportional to the number of the loop cycles. And the space complexity would be O(1) since no n-dependent extra space is needed other than that for storing the Fibonacci sequence.
Naive Fibonacci
To generate Fibonacci numbers, the most straight forward approach is via a basic recursive function like below:
|
1 2 3 4 5 6 7 8 9 10 11 |
def fib(n: Int): BigInt = n match { case 0 => 0 case 1 => 1 case _ => fib(n-2) + fib(n-1) } (0 to 10).foreach(n => print(fib(n) + " ")) // 0 1 1 2 3 5 8 13 21 34 55 fib(50) // res1: BigInt = 12586269025 |
With such a naive recursive function, computing the 50th number, i.e. fib(50), would take minutes on a typical laptop, and attempts to compute any number higher up like fib(90) would most certainly lead to an infinite run.
Tail recursive Fibonacci
So, let’s come up with a tail recursive method:
|
1 2 3 4 5 6 7 8 9 10 |
def fibTR(num: Int): BigInt = { @scala.annotation.tailrec def fibFcn(n: Int, acc1: BigInt, acc2: BigInt): BigInt = n match { case 0 => acc1 case 1 => acc2 case _ => fibFcn(n - 1, acc2, acc1 + acc2) } fibFcn(num, 0, 1) } |
As shown above, tail recursion is accomplished by means of a couple of accumulators as parameters for the inner method to recursively carry over the two numbers that precede the current number.
With the Fibonacci TailRec version, computing, say, the 90th number would finish instantaneously.
|
1 2 |
fibTR(90) // res2: BigInt = 2880067194370816120 |
Fibonacci in a Scala Stream
Another way of implementing Fibonacci is to define the sequence to be stored in a “lazy” collection, such as a Scala Stream:
|
1 2 3 4 |
val fibS: Stream[BigInt] = 0 #:: fibS.scan(BigInt(1))(_ + _) fibS(90) // res3: BigInt = 2880067194370816120 |
Using method scan, scan(1)(_ + _) generates a Stream with each of its elements being successively assigned the sum of the previous two elements. Since Streams are “lazy”, none of the element values in the defined fibStream will be evaluated until the element is being requested.
While at it, there is a couple of other commonly seen Fibonacci implementation variants with Scala Stream:
|
1 2 3 4 5 6 |
val fibS: Stream[BigInt] = 0 #:: 1 #:: (fibS zip fibS.tail).map(n => n._1 + n._2) val fibS: Stream[BigInt] = { def fs(prev: BigInt, curr: BigInt): Stream[BigInt] = prev #:: fs(curr, prev + curr) fs(0, 1) } |
Scala Stream memoizes by design
These Stream-based Fibonacci implementations perform reasonably well, somewhat comparable to the tail recursive Fibonacci. But while these Stream implementations all involve recursion, none is tail recursive. So, why doesn’t it suffer the same performance issue like the naive Fibonacci implementation does? The short answer is memoization.
Digging into the source code of Scala Stream would reveal that method #:: (which is wrapped in class ConsWrapper) is defined as:
|
1 |
def #::[B >: A](hd: B): Stream[B] = cons(hd, tl) |
Tracing method cons further reveals that the Stream tail is a by-name parameter to class Cons, thus ensuring that the concatenation is performed lazily:
|
1 |
final class Cons[+A](hd: A, tl: => Stream[A]) extends Stream[A] |
But lazy evaluation via by-name parameter does nothing to memoization. Digging deeper into the source code, one would see that Stream content is iterated through a StreamIterator class defined as follows:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
final class StreamIterator[+A] private() extends AbstractIterator[A] with Iterator[A] { def this(self: Stream[A]) { this() these = new LazyCell(self) } class LazyCell(st: => Stream[A]) { lazy val v = st } private var these: LazyCell = _ def hasNext: Boolean = these.v.nonEmpty def next(): A = if (isEmpty) Iterator.empty.next() else { val cur = these.v val result = cur.head these = new LazyCell(cur.tail) result } ... } |
The inner class LazyCell not only has a by-name parameter but, more importantly, makes the Stream represented by the StreamIterator instance a lazy val which, by nature, enables memoization by caching the value upon the first (and only first) evaluation.
Memoized Fibonacci using a mutable Map
While using a Scala Stream to implement Fibonacci would automatically leverage memoization, one could also explicitly employ the very feature without Streams. For instance, by leveraging method getOrElseUpdate in a mutable Map, a memoize function can be defined as follows:
|
1 2 3 4 5 6 |
// Memoization using mutable Map def memoize[K, V](f: K => V): K => V = { val cache = scala.collection.mutable.Map.empty[K, V] k => cache.getOrElseUpdate(k, f(k)) } |
For example, the naive Fibonacci equipped with memoization via this memoize function would instantly become a much more efficient implementation:
|
1 2 3 4 5 6 7 8 |
val fibM: Int => BigInt = memoize(n => n match { case 0 => 0 case 1 => 1 case _ => fibM(n-2) + fibM(n-1) }) fibM(90) // res4: BigInt = 2880067194370816120 |
For the tail recursive Fibonacci fibTR, this memoize function wouldn’t be applicable as its inner function fibFcn takes accumulators as additional parameters. As for the Stream-based fibS which is already equipped with Stream’s memoization, applying memoize wouldn’t produce any significant performance gain.