🦸‍♂️ Coding Interview Hero 🦸‍♀️

Fibonacci suite

Exercice: compute n^th element of Fibonacci suite using a recursive function. F₀ = F₁ = 1 and F_n+2 = F_n+1 + F_n

You can assume n is positive.

        def fibonacci(n: Int): BigInt = n match {
  case 0 | 1 => n
  case _ => Fibonacci(n - 2) + Fibonacci(n - 1)
}
      

Question: what is the time complexity? $$ T_n = T_{n-1} + T_{n-2} + O(1) $$

We can approximate lower and upper bounds: $$ O(2^{\frac{n}{2}}) \leq T_n \leq O(2^n) $$

And if you are good at maths (useful inputs here), you can even prove that: $$ T_n = O(\phi^n) $$

This is really poor (exponential complexity) and on an average laptop it will take several seconds just to compute the 20th element. To be more concrete, let's use JMH (why you should always use JMH) to run a benchmark:

        package fibonacci

import org.openjdk.jmh.annotations.{Benchmark, Fork, Measurement, Warmup}
import org.openjdk.jmh.infra.Blackhole

class FibonacciBenchmark {
  def fibonacci(n: Int): BigInt = n match {
    case 0 | 1 => n
    case _ => fibonacci(n - 2) + fibonacci(n - 1)
  }

  def iterativeFibonacci(n: Int): BigInt = {
    var a: BigInt = 0
    var b: BigInt = 1
    var i = 0

    while (i < n) {
      val tmp: BigInt = a + b
      a = b
      b = tmp
      i = i + 1
    }

    a
  }

  @Benchmark
  @Warmup(iterations = 2)
  @Fork(value = 2)
  @Measurement(iterations = 2)
  def recursive(blackHole: Blackhole): BigInt = {
    val fib20 = fibonacci(20)
    blackHole.consume(fib20)
    fib20
  }

  @Benchmark
  @Warmup(iterations = 2)
  @Fork(value = 2)
  @Measurement(iterations = 2)
  def iterative(blackHole: Blackhole): BigInt = {
    val fib20 = iterativeFibonacci(20)
    blackHole.consume(fib20)
    fib20
  }
}
      

Then running sbt run jmh:run will produce such output:

Benchmark	Mode	Threads	Samples	Score	Score Error (99,9%)	Unit
fibonacci.FibonacciBenchmark.recursive	thrpt	1	4	5962,057514	557,707975	ops/s
fibonacci.FibonacciBenchmark.iterative	thrpt	1	4	3703413,835	308887,785	ops/s

Exercice: use the tail recursion to improve the performances.

        @tailrec
private def tailRecFibonacci(n: Int, a: BigInt = 0, b: BigInt = 1) : BigInt = n match {
  case 0 => a
  case 1 => b
  case _ => tailRecFibonacci(n - 1, b, a + b)
}
      

Question: what is the time complexity? $$ T_n = O(n) $$

Let's add a benchmark and compare the results:

Benchmark	Mode	Threads	Samples	Score	Score Error (99,9%)	Unit
fibonacci.FibonacciBenchmark.recursive	thrpt	1	4	5962,057514	557,707975	ops/s
fibonacci.FibonacciBenchmark.tailRecursive	thrpt	1	4	4008972,107	104654,183	ops/s
fibonacci.FibonacciBenchmark.iterative	thrpt	1	4	3703413,835	308887,785	ops/s

Question: does the @tailrec annotation change the performaces?

Answer: no. It's only used by the compiler to verify for you if your function is tail recursive. If not, you will have a compile error. You can check the benchmark on github

All code is available on github.