generic implementation approaches for a recursive function

Question

Let's take the famous fibonacci problem as an example but this is a generic problem. Also, taking scala as the language as it's rather feature-rich. I want to know which solution you'd prefer.

we all know that the following implementation is evil as it's not stack-safe:

//bad!
def naiveFib(n: Int): BigInt = {
  if (n <= 1)
    1
  else
    naiveFib(n - 1) + naiveFib(n - 2)
}

we can improve it and make it tail-recursive and stack-safe:

def fibStackSafe(n: Int): BigInt = {
  @tailrec
  def internally(cycles: Int, last: BigInt, next: BigInt): BigInt =
    if (cycles > 0)
      internally(cycles-1, next, last+next)
    else
      next
  internally(n - 2 , last = 1, next = 1)
}

acceptable solution. Equally acceptable, is a solution like:

def fibByEval(n: Int): BigInt = {
  def internally(cycles: Int, last: BigInt, next: BigInt): Eval[BigInt] =
    Eval.always(cycles > 0).flatMap {
      case true =>
        internally(cycles-1, next, last+next)
      case false =>
        Eval.now(next)
    }
  internally(n - 2 , last = 1, next = 1).value
}

which uses cats's Eval/Monix's Coeval (slight difference between the two, feel free to comment on your preference) which guarantees stack-safety by definition. Although an Eval-powered function can still lack heap-safety and give you memory error. It does win you a few other things too.

Here is a Stream/LazyList attempt which uses the concepts of lazy-evaluation:

def fibByZip(n: Int): BigInt = {
  def inner:Stream[Pure, BigInt] = Stream(BigInt(1)) ++ Stream(BigInt(1)) ++ (inner zip inner.tail).map{ t => t._1 + t._2 }
  inner.drop(n-1).take(1).compile.toVector.head
}

this one comes with the feature/overhead of internally "caching" the intermediate results.

Here is a more/less (depending on your point of view) readable version of the above:

def fibByScan(n: Int): BigInt = {
  def inner: Stream[Pure, BigInt] = Stream(BigInt(1)) ++ inner.scan(BigInt(1))(_ + _)
  inner.drop(n-1).take(1).compile.toVector.head
}

and finally, here is an effect-full approach which uses fs2 streams and cats's Ref:

def fibStream(n: Int): IO[Int] = {
  val internal = {
    def getNextAndUpdateRefs(twoBefore: Ref[IO, Int], oneBefore: Ref[IO, Int]): IO[Int] = for {
      last <- oneBefore.get
      lastLast <- twoBefore.get
      _ <- twoBefore.set(last)
      result = last + lastLast
      _ <- oneBefore.set(result)
    } yield result

    for {
      twoBefore <- Stream.eval(Ref.of[IO, Int](1))
      oneBefore <- Stream.eval(Ref.of[IO, Int](1))
      _ <- Stream.emits(Range(0, n-2))
      res <- Stream.eval(getNextAndUpdateRefs(twoBefore, oneBefore))
    } yield res
  }

  internal.take(n).compile.lastOrError
}

it's not pure but it's thread-safe and pretty readable.

The code starts simple but will change in the future and needs to be maintained.

• model changing whereas instead of using the last two entries, you might need the last three elements.

• you want to easily debug it and/or reason about it.

• you want to easily and efficiently test it

• the model might become numerical and non-exact so you might want to test it for more than just correctness.

• model will become async to calculate.

• might need to introduce parallelism.

I appreciate we should be agile and not future proof things too much, but I am interested to know which option people would go for, considering the following criteria:

• readability
• conciseness
• flexibility to maintain
• performance

feel free to mention other criteria I might be ignoring here.