尾递归问题

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) 
  }
}

这段代码出现了栈溢出错误（在这里提问非常恰当！）。我本以为它是尾递归优化的。那么出了什么问题呢？

- maasg

---

实际上，如果头元素大于其后面的元素，则会产生“true”，例如3,2,1。 - Pablo Fernandez

不是直接与您的问题相关，但请注意您的 case x::y::Nil 是多余的，并且您的 case x::y::tail 有错误（考虑 List(3,2,9)）。 - dave4420

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
  }
}

- Kim Stebel

---

未来读者参考：虽然这个回答正确地解释了为什么算法不是尾递归优化的，但请注意，正如其他人正确指出的那样，该算法是错误的。@Luigi Plinge的回答虽然没有涉及问题的关键要素，但包含了该算法的修正版本。 - maasg

真的。我根本没有检查算法。 - Kim Stebel

很有趣的是，尽管这个答案获得了14个赞，但它是不完整的：如果你在原始版本前面加上@tailrec，并将位运算符&更改为正确的版本&&，编译器就能够使其成为尾递归。因此，问题在于使用的运算符而不是其位置。 - Luigi Plinge

@Luigi Plinge，您能否更新您的答案，并简要解释一下为什么它有效吗？希望能为这个问题提供一个好的、完整的答案。这不是SO的理念吗？ - maasg

@maasg 我猜测，但 认为 编译器只能使用 && 进行尾递归，因为它是一个短路运算符。如果你仔细想一下，它不需要保留以前的堆栈帧，因为如果 RHS 被评估，则返回值仅取决于 RHS。 - Luigi Plinge

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

- Luigi Plinge

---

我看到了我的算法中的缺陷。谢谢。我猜你也可以做 isOrdered(y::t)，以保持表达式在情况的上下文中。 - maasg

@maasg 不要这样做：执行时间会增加三倍。你可以写成 case x :: t => if (x <= t.head) isOrdered(t) else false，它相当于上述代码，并避免引入额外的 y 变量。 - Luigi Plinge

有趣而且出乎意料的接近。我的执行速度慢了x2.6倍。你介意说一下原因吗？cons应该是O(1)的。 - maasg

@maasg 我对细节有点模糊，但我知道 head 和 tail 是免费的：它们只返回 :: case class 的私有字段 hd 和 tl 的值。当您开始获取其他子列表时，我想需要创建新的 case class 实例。这是每次递归的固定开销，但如果您进行 n 次 O(1) 操作，则总体效果为 O(n)。 - Luigi Plinge

我一直在思考这个问题，并找到了我认为是一个不错的惯用解决方案：list.foldLeft((true,list.head))((x,y)=>(x._1 && x._2<y,y))._1。缺点是它不能像递归版本那样在第一次出现无序元素时进行快速处理。 - maasg

Answer 3

它不能进行尾递归优化，因为您返回了这个：'x>y & isOrdered(tail)'。这意味着它需要在堆栈上保留它。

使用@tailrec注释来强制出现错误，当您期望函数进行尾递归时。它还会解释为什么无法进行尾递归优化。

- thoredge

Answer 4

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

使用&&或if语句可能会有所帮助。

- MattK