Scala:尾递归和 ListBuffer

Question

我正在学习 Scala，在学习过程中，我遵循了 Brien (http://www.knowing.net/index.php/2006/06/16/15-exercises-to-know-a-programming-language-part-1/) 的 15 个练习。在第二个练习中，我应该实现 Haar 转换。我实现了大部分但是在尾递归的返回值上挣扎了几个小时。由于编译器不编译 ++ - 或者更确切地说 haar(averages)++ haar(averagesD) 行。

• 我在递归函数中做错了什么？
• 您能否就我的代码提供其他反馈？

代码:

import scala.collection.mutable.ListBuffer
import scala.annotation.tailrec

object haarWavelet2 {

  def avg(tpl:Tuple2[Double, Double]):Double = (tpl._1 + tpl._2) / 2.
  def avgD(tpl:Tuple2[Double, Double]):Double = (tpl._1 - tpl._2) / 2
  def total_avg(nums:ListBuffer[Double]):Double = nums.sum / nums.length

  @tailrec 
  def haar(nums:ListBuffer[Double]):ListBuffer[Double] = {

    if (nums.length == 1) {return nums}

    val buffer = new ListBuffer[Tuple2[Double, Double]]
    for (i <- 0 to nums.length-1 by 2) buffer.append((nums(i), nums(i+1)))

    val averages = for(tpl <- buffer) yield avg(tpl)
    val averagesD = for(tpl <- buffer) yield avgD(tpl)

    haar(averages) ++ haar(averagesD) // does not compile
    }

  def main(args: Array[String]): Unit = {
          print(haar(ListBuffer(8., 5., 6., 2.)))
  }
}

Answer 1

尾递归具有以下形式:

def func(x..., value){
  if(condition) return value
  else func(y..., value')
}

如果您查看此表单，您会看到，为了评估 func，我需要的只是 func 本身，但具有一组不同的参数。因此，栈上只有一项，很容易转化为迭代算法。

你的实现看起来像这样:

def func(x...){
  if(condition) return value
  else func(y...) + func(z...)

请注意，为了计算 func，您必须首先计算 func，运算符 +，然后再次计算“func”。因此，这 3 个项目需要以非常真实的评估顺序放置在堆栈中，不适合尾调用优化。