递归函数 throw StackOverflowError

Question

我在这个功能上遇到了问题。我需要处理超过100万条记录，但是这个函数崩溃了。看起来只是对数千条记录有效，对更大的列表会抛出一个StackOverflowError。有什么建议吗？

def split(list: List[(Pair, Boolean)]): List[List[Pair]] = list match {
  case Nil => Nil
  case head :: tail => {
    val (l1, l2) = tail.span(!_._2)
    (head :: l1).map(_._1) :: split(l2)
  }
}

Answer 1

你的程序会抛出一个StackOverflow异常。

Exception in thread "main" java.lang.StackOverflowError
    at scala.collection.immutable.List.map(List.scala:283)

原因很简单，因为你的方法不是尾部递归的如果你用@tailrec注释它，它就不会被编译。

  @tailrec
  def split(list: List[(Pair, Boolean)]): List[List[Pair]] = list match {
    case Nil => Nil
    case head :: tail => {
      val (l1, l2) = tail.span(!_._2)
      (head :: l1).map(_._1) :: split(l2)
    }
  }

解决的办法是把你的递归方法做成尾部递归，或者用某种循环来代替。

你可以试试这样的东西。

 @tailrec
  def split(list: List[(Pair, Boolean)], accumulator:  List[List[Pair]] = List[List[Pair]]()): List[List[Pair]] = list match {
    case Nil => accumulator
    case head :: tail => {
      val (l1, l2) = tail.span(!_._2)
      split(l2, (head :: l1).map(_._1)::accumulator)
    }
  }