将球函数转换为尾递归函数

Question

我已经在 Scala 中实现了 Sphere 函数（获取元素列表，对每个元素求平方和 returns 总和）。我想将此函数转换为尾递归。我的代码在这里

def Sphere(list: List[Double]): Double = {
  val power = list.map(math.pow(_, 2))
  power.reduce(_+_)
}

Answer 1

看起来像：

  @tailrec
  def Sphere(list: List[Double], result: Double = 0): Double = list match {
    case Nil => result
    case x::xs => Sphere(xs, result + math.pow(x, 2))
  }

  println(Sphere(List(1,3,4,5)))

使用 @tailrec 确保它实际上是尾递归的（编译将失败）。

重要的是：

最后一个电话是给自己的
它在参数列表中有中间结果
x 是您进行计算的列表的头部
xs 是列表的其余部分（tail）——在其中附加递归函数——直到列表为空 > Nil .

Answer 2

如果要保持相同的函数签名，则需要使用嵌套递归函数：

def Sphere(list: List[Double]): Double = {
  @annotation.tailrec
  def loop(rem: List[Double], res: Double): Double =
    rem match {
      case hd :: tail => loop(tail, res + hd*hd)
      case _ => res
    }

  loop(list, 0)
}

您可以将其编写为单个 tail-recursive 函数，但这需要更改函数签名以添加虚假的额外参数。这可以说是糟糕的设计，因为实现通过接口泄漏了出去。这也要求函数如果是方法就标明final

Answer 3

加上上面的答案，如果你使用 foldLeft，它已经优化了尾调用

def Sphere(list: List[Double]): Double = {
    list.foldLeft(0.0)((res, elem) => res + elem * elem)
}

最好使用库版本，并且在可用时不要为编译器添加额外检查 (@tailrec)。

**foldLeft 与reduceLeft 相同，只是它需要一个额外的初始值作为参数，并且当集合为空时不会抛出异常。

**foldLeft 的实际实现出于性能原因最终使用 while 循环，但这又是尾递归的好处，使其与循环一样快。

将球函数转换为尾递归函数

Convert sphere function to tail recursive function

scala

tail-recursion