scalatail-recursion

# Making recursive code, tail recursive in Scala

I'd like to change the code to be tail recursive not to overflow the stack expression is an ADT of Label or Tree

``````  def combine[A](expression: Expression, runners: List[Runner[A]]): Runner[A] = {
val labelToHashmap = runners.map(runner=> (runner.label.get, runner)).toMap
def reduceExpression(e: Expression): Runner[A] = {
e match {
case Label(_, value) => labelToHashmap(value)
case Tree(_, operation, left, right) =>
operation match {
case AND =>  reduceExpression(left).and(reduceExpression(right))
case OR => reduceExpression(left).or(reduceExpression(right))
}
}
}
reduceExpression(expression)
}
``````

How can I turn the above code to a tail recursive one?

Solution

• You can rewrite the function in a tail-recursive way like Kolmar has shown, and it'll work. But I think this usually obscures the intent of the algorithm, because now you have to fiddle around with an explicit stack that is normally implicit.

I would say it's better to factor out the stack fiddling bits into a re-usable data structure and use that. The `cats.Eval` type is such a data structure.

``````import cats.Eval
import cats.syntax.all._

def combine[A](
expression: Expression,
runners: List[Runner[A]]
): Runner[A] = {
val labelToHashmap = runners.fproductLeft(_.label.get).toMap
def reduceExpression(e: Expression): Eval[Runner[A]] =
Eval.now(e).flatMap {
case Label(_, value) => labelToHashmap(value)
case Tree(_, operation, left, right) =>
operation match {
case AND =>
(
reduceExpression(left),
reduceExpression(right)
).mapN(_ and _)
case OR =>
(
reduceExpression(left),
reduceExpression(right)
).mapN(_ or _)
}
}
reduceExpression(expression).value
}
``````

As you can see, this essentially retains the logic of the straight-up recursive implementation, but it's nevertheless stack-safe due to the way `Eval`'s `value` method is implemented.

Also check out the documentation: https://typelevel.org/cats/datatypes/eval.html