Making recursive code, tail recursive in Scala

Question

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?

Answer 1

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