尾递归问题

Question

我们正在 Scala 中试验并行集合，并想检查结果是否有序。为此，我在 REPL 上编写了一个小函数来对我们正在生成的非常大的列表进行检查：

def isOrdered(l:List[Int]):Boolean = { l match { 
  case Nil => true
  case x::Nil => true
  case x::y::Nil => x>y
  case x::y::tail => x>y & isOrdered(tail) 
  }
}

它因 stackOverflow 而失败（对于这里的问题来说多么合适！）。 我期待它能进行尾部优化。怎么了？

Answer 1

isOrdered 不是代码中的最后一个调用， &运营商群岛。试试这个：

@scala.annotation.tailrec def isOrdered(l:List[Int]):Boolean = { l match { 
  case Nil => true
  case x::Nil => true
  case x::y::Nil => x>y
  case x::y::tail => if (x>y) isOrdered(tail) else false
  }
}

Answer 2

你的算法不正确。即使 @Kim 进行了改进，isOrdered(List(4,3,5,4)) 仍返回 true。

试试这个：（

def isOrdered(l:List[Int]): Boolean = l match {
  case Nil => true
  case x :: Nil => true
  case x :: y :: t => if (x <= y) isOrdered(l.tail) else false
}

也更新了，以便标志正确）

编辑：我的首选布局是这样的：

def isOrdered(list: List[Int]): Boolean = list match {
  case Nil      => true
  case x :: Nil => true
  case x :: xs  => if (x > xs.head) false
                   else isOrdered(xs)
}

如果性能不是问题，快速方法是

def isOrdered(l: List[Int]) = l == l.sorted

Answer 3

它不能进行尾部优化，因为您返回：'x>y & isOrdered(尾部)'。这意味着需要将其保留在堆栈中。

当您期望函数是尾递归时，使用 @tailrec 注释强制发生错误。它还将解释为什么不能。

Answer 4

我认为问题在于您在最后一种情况下使用了按位与运算符（&）。由于运行时需要知道 isOrdered 调用的值才能计算 &，因此它无法对该函数进行尾部优化。 （也就是说，在调用 isOrdered 之后，还有更多的代码要运行——按位与运算。

）或者 if 语句可能会有所帮助。