visitors-1.scala

trait SACVisitor[R] {
  def c1(a: Int): R
  def c2(a: R, b: R): R
}

sealed trait SAC extends Product with Serializable {
  def fold[R](visitor: SACVisitor[R]): R
}

object SAC {
  final case class C1(a: Int) extends SAC {
    def fold[R](visitor: SACVisitor[R]): R =
      visitor.c1(a)
  }

  final case class C2(a: SAC, b: SAC) extends SAC {
    def fold[R](visitor: SACVisitor[R]): R =
      // Explicit recursive calls in the "recursive points".
      visitor.c2(a.fold(visitor), b.fold(visitor))
  }

  def sum(sac: SAC): Int =
    sac.fold(new SACVisitor[Int] {
      override def c1(a: Int) = a
      // Recursive points have already been handled, folded, by `fold`.
      override def c2(a: Int, b: Int) = a + b
    })
}

visitors-2.scala

// Alternatively, `fold` could be defined in the base trait using pattern matching.

trait SACVisitor[R] {
  def c1(a: Int): R
  def c2(a: R, b: R): R
}

sealed trait SAC extends Product with Serializable {
  final def fold[R](visitor: SACVisitor[R]): R =
    this match {
      case SAC.C1(a) => visitor.c1(a)
      case SAC.C2(a, b) => visitor.c2(a.fold(visitor), b.fold(visitor))
    }
}

object SAC {
  final case class C1(a: Int) extends SAC
  final case class C2(a: SAC, b: SAC) extends SAC

  def sum(sac: SAC): Int =
    sac.fold(new SACVisitor[Int] {
      override def c1(a: Int) = a
      override def c2(a: Int, b: Int) = a + b
    })
}