进行递归调用，使用尾递归优化

Question

我有下面这个递归函数

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

我想不到一种方法使得sequenceNumber成为尾递归函数。

- Sam

---

@Sam-d，你应该把“ProductionRule”特质添加到你的代码示例中，这样整个代码才能编译。 - Bogdan Vakulenko

Answer 1

将方法转换为尾递归的思想是将每个计算步骤放入累加器中，然后将此累加器传回到方法中，以便在下一步中您可以返回累加器或使用根据您的步骤修改的新累加器再次调用此方法。

因此，您将获得类似于以下内容：

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

  }

}

但是需要说明的是，有一种更高级的技术来构建尾递归，叫做Trampoling，例如可以使用scala.util.control.TailCalls实现。

我不太擅长这种技术，但它大概是像这样的：

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 无法在此标记为尾递归，但实际上是在“后台”中进行了尾递归。若要获得真正的计算结果，您需要调用 sequenceNumber(done(...),done(...)).result

- Bogdan Vakulenko

Answer 2

也许贴出的代码过于简化，但看起来你实际上并不需要program()或递归。 program(seed)实际上只是seed.flatMap(rule.generate)，因此递归展开为seed.flatMap(rule.generate).flatMap(rule.generate).flatMap(...等，这正是iterate()将为您执行的操作。

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

- jwvh