将循环问题转换为Scala中的递归解

Question

我编写了以下方法（工作得很好），该方法接受一个列表并返回包含以下内容的列表的列表：元素，因此第一个列表包含列表元素的一半，第二个列表包含其余元素的一半，依此类推。例如，

repHalve(List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15))

返回：

List(List(1, 2, 3, 4, 5, 6, 7, 8), List(9, 10, 11, 12), List(13, 14), List(15))

问题是我是Scala的新手，想将此方法转换为递归方法。请让我知道该如何转换。我知道基本情况可能与while循环中的条件相同，但仍然无法弄清楚。任何帮助将不胜感激。谢谢

def repHalve(list:List[Any]){

    var local_list:List[Any] = list
    var list_of_lists:List[Any] = List.empty

    while(local_list.length>1){
      val sub = local_list.slice(0, (local_list.length/2)+1)
      list_of_lists  ++= List(sub)
      local_list = local_list.slice(local_list.length/2+1, local_list.length)
    }

    list_of_lists ++= List(List(list.last))
    println(list_of_lists)
  }

Answer 1

这里是完全tail-recursive实现。如果您有任何问题，请告诉我。

def repHalve[T](list: List[T]): List[List[T]] = {
  def half(i: Int): Int = 
    if ((i % 2) == 0) i / 2 else (i + 1) / 2

  @annotation.tailrec
  def loop(remaining: List[T], targetLength: Int, acc: List[List[T]]): List[List[T]] =
    remaining match {
      case Nil => acc.reverse

      case list =>
        @annotation.tailrec
        def innerLoop(remaining: List[T], currentLength: Int, acc: List[T]): (List[T], List[T]) =
          remaining match {
            case x :: xs =>
              if (currentLength != targetLength)
                innerLoop(remaining = xs, currentLength + 1, x :: acc)
              else
                (x :: xs, acc.reverse)
            case Nil =>
              (Nil, acc.reverse)
          }

        val (remaining, newList) = innerLoop(remaining = list, currentLength = 0, acc = List.empty)
        loop(remaining, half(targetLength), newList :: acc)
    }

  loop(remaining = list, targetLength = half(list.length), acc = List.empty)
}

您可以这样使用：

repHalve((1 to 20).toList)
// res: List[List[Int]] = List(List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10), List(11, 12, 13, 14, 15), List(16, 17, 18), List(19, 20))

Answer 2

考虑路易斯的类似解决方案，但使用splitAt

def repHalve(l: List[Int]): List[List[Int]] = {
  def half(i: Int): Int = if ((i % 2) == 0) i / 2 else (i + 1) / 2

  @annotation.tailrec
  def loop(l: List[Int], size: Int, acc: List[List[Int]]): List[List[Int]] = l match {
    case x :: Nil => (List(x) :: acc).reverse
    case _ =>
      val (left, right) = l.splitAt(half(size))
      loop(right, right.size, left :: acc)
  }
  loop(l, l.size, Nil)
}