0

如果函数中的最后一条语句是 func(x,tailList)：

    def func(x:Int):List[Int]...
    case head :: tailList => head :: func(x,tailList)

将此函数转换为尾递归需要将累加器添加为第三个参数（并在 func() 中添加本地函数以保持其干净）。 

    insertTail(x,tailList,head::acc)

似乎无法正常工作。“acc”不应该保持正在进行的计算吗？

我是否在这里遗漏了一些东西以使其与累加器进行尾递归工作？

添加更完整的示例

def funcTailTest(x:Int,xs:List[Int]):List[Int] =  {
@tailrec
def inner(x:Int,xs:List[Int],acc:List[Int]) : List[Int] = xs match {

  case head::tailList => {
    inner(x,tailList,head::acc)
  }
}
inner(x,xs,Nil)

}

基本上 head 应该被添加到 inner() 函数的输出中，所以如果没有尝试使其尾部递归最后一个语句在一个案例中看起来

head::inner(x,tailList)
4

2 回答 2

1

假设 reverse 也是尾递归实现的（肯定可以），以下是尾递归追加：

def append[T](y: T, xs: List[T]): List[T] = {
  @tailrec
  def appendAcc[T](y: T, xs: List[T], acc: List[T]): List[T] = xs match {
    case Nil => y :: acc
    case x :: xs => appendAcc(y, xs, x :: acc)
  }

  appendAcc(y, xs, Nil).reverse
}
于 2012-07-25T14:16:51.413 回答
1

以下是使用 cons 运算符实现尾递归的 scala 函数

def reverseUtility(ele: List[Int], res: List[Int]):List[Int] ={
  ele match {
  case Nil => Nil
  case x :: Nil => x :: res
  case x :: y => reverseUtility(y, (x::res))
}}

传递一个列表Int和一个空列表res(result)作为函数的参数。该函数的时间复杂度为 O(N)

于 2015-05-13T10:31:38.223 回答