# generic implementation approaches for a recursive function

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 }
}


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))(_ + _)
}


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
}


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: