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

Question

我写了下面的方法（工作得很好），它接受一个列表和 returns 一个包含列表的列表元素，因此第一个列表包含列表元素的一半，下一个列表包含剩余元素的一半，依此类推。例如，

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

这是一个完全尾递归实现。
如果您有任何问题，请告诉我。

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

考虑与 Luis 类似的解决方案，但使用 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)
}

jmh 基准测试使用 (1 to 200).toList 作为输入表明 Luis 的解决方案更快

[info] So60178352._luis   thrpt    5  666357.490 ± 165323.129  ops/s
[info] So60178352._mario  thrpt    5  591174.959 ± 118097.426  ops/s

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

Convert Loop problem to Recursive Solution in Scala

scala

recursion

tail-recursion