调用多个递归调用时允许@tailrec 的结构

Question

以下逻辑确定总和为 n 并产生最大乘积的整数组合：

def bestProd(n: Int) = {
  type AType = (Vector[Int],  Long)
  import annotation._
  // @tailrec  (umm .. nope ..)
  def bestProd0(n: Int, accum : AType): AType  = {
    if (n<=1) accum
    else {
      var cmax = accum
      for (k <- 2 to n) {
        val tmpacc = bestProd0(n-k, (accum._1 :+ k, accum._2 * k))
        if (tmpacc._2 > cmax._2) {
          cmax = tmpacc
        }
      }
      cmax
    }
  }
  bestProd0(n, (Vector(), 1))
}

此代码确实有效：

scala> bestProd(11)
res22: (Vector[Int], Long) = (Vector(2, 3, 3, 3),54)

现在，@tailrec 不起作用对我来说并不奇怪。毕竟递归调用在尾部位置是not。是否可以重新制定 for 循环，而不是进行适当的单次调用来实现尾递归？

Answer 1

我认为如果您试图坚持规定的算法是不可能的。重新考虑你可以做这样的事情的方法。

import scala.annotation.tailrec
def bestProd1(n: Int) = {
  @tailrec
  def nums(acc: Vector[Int]): Vector[Int] = {
    if (acc.head > 4)
      nums( (acc.head - 3) +: 3 +: acc.tail )
    else
      acc
  }
  val result = nums( Vector(n) )
  (result, result.product)
}

除了我没有将 4 拆分为 2,2.

之外，它得出了相同的结果（据我所知）

调用多个递归调用时允许@tailrec 的结构

Structure to allow @tailrec when multiple recursive calls are invoked

scala

recursion

tail-recursion