Making recursive call, tail recursive

Question

I have the following recursive function

trait SequenceGenerator[T] {
  def program(l: List[T])(implicit rule: ProductionRule[T]): List[T] = {
    l.flatMap(rule.generate)
  }

  def sequenceNumber(seed: List[T], number: Int)(implicit rule: ProductionRule[T]): List[T] = {
    number match {
      case 1 => program(seed)
      case a => program(sequenceNumber(seed, a - 1))
    }
  }
}

I can't think of a way to make sequenceNumber tail recursive.

Answer 1

The idea behind transforming methods to tailrec is to put every next calculation step into accumulator and then pass this accumulator back to the method, so that on next step you could return your accumulator or call this method again with new accumulator modified according to your step.

So you will get something like this:

trait SequenceGenerator[T] {

  def program(l: List[T])(implicit rule: ProductionRule[T]): List[T] = l.flatMap(rule.generate)

  def sequenceNumber(seed: List[T], number: Int)(implicit rule: ProductionRule[T]): List[T] = {

    @tailrec
    def tailRec(number: Int, acc: List[T]): List[T] =  number match {
      case 1 => acc
      case a => tailRec(a-1,program(acc))
    }

    tailRec(number,program(seed))

  }

}

But just FYI there is also more advanced technique for building tail recursions called Trampoling. It can be implemented using scala.util.control.TailCalls for example.

I'm not very good in this technique but it will look something like this:

import TailCalls._

trait SequenceGenerator[T] {

  def program(l: TailRec[List[T]])(implicit rule: ProductionRule[T]):TailRec[List[T]] = {
    l.map(_.flatMap(rule.generate))
  }

  def sequenceNumber(seed: TailRec[List[T]], number: TailRec[Int])(implicit rule: ProductionRule[T]): TailRec[List[T]] = {
    number flatMap {
      case 1 => tailcall(program(seed))
      case a => tailcall(program(sequenceNumber(seed, done(a - 1))))
    }
  }

}

sequenceNumber can't be marked as tailrec here but it actually tailrec in "background". To get real calculation result you will need to call sequenceNumber(done(...),done(...)).result

Answer 2

Perhaps the posted code is an over-simplification, but it looks like you don't actually need program(), or recursion for that matter.

program(seed) is really just seed.flatMap(rule.generate) and so the recursion rolls out to seed.flatMap(rule.generate).flatMap(rule.generate).flatMap(... etc., which is what iterate() will do for you.

def sequenceNumber(seed:List[T], number:Int)(implicit rule:ProductionRule[T]):List[T] =
  Seq.iterate(seed.flatMap(rule.generate), number)(_.flatMap(rule.generate)).last