拖尾的尾递归实现

Question

我正在对In_Shuffle使用递归，但传递给该方法的列表却与递归基本情况混淆了。由于Scala不允许您修改传递的参数，因此我无法将新值分配给传递的列表。这是我的代码：

def shuffle(list1: List[Any], list2: List[Any]): List[Any] = {
    list1.zipAll(list2, "", "")
      .flatMap(_.productIterator.toList)
      .filter(_ != "")
  }

def splitLists(list: List[Any], n: Int) = {
    if (n > list.length) {
      throw new Exception("N is greater than length of list")
    }
    else if (n == list.length) {
      List(list, List())
    }
    else {
      List(list.slice(0, n),
        list.slice(n, list.length))
    }
  }

以下方法处于无限循环中。我知道问题出在我要初始化list变量的第一行。

  @annotation.tailrec
  def in_shuffle(list:List[Any], org_list:List[Any]):Any={
    var list:List[Any] = List()
    if (list.equals(org_list)) return true
    if (list.length<1) {
      list=org_list
    }
    val div_list = splitLists(list, list.length/2)
    list = shuffle(div_list(0), div_list(1))
    in_shuffle(list, org_list)
  }

In-Shuffle正在使用以下代码调用。

println(in_shuffle(List(), (1 to 4).toList))任何帮助将不胜感激。谢谢。

Answer 1

您的代码很少有问题。我们尝试避免使用Any，而不是

def shuffle(list1: List[Any], list2: List[Any]): List[Any]

我们使用类型参数T

def shuffle(t: (List[T], List[T])): List[T]

接下来我们flatten a list of tuples这样

def shuffle(t: (List[T], List[T])): List[T] =
  t._2 zip t._1 flatMap { case (a, b) => List(a, b) }

接下来，我们使用现成的splitAt而不是滚动自己的splitAt

splitLists

最后，我们避免使用val (left, right) = list.splitAt(list.size/2) 。将所有内容放在一起]

return

注意

def in_shuffle[T](original: List[T]) = {
  require(original.size % 2 == 0, "In shuffle requires even number of elements")

  def shuffle(t: (List[T], List[T])): List[T] =
    t._2 zip t._1 flatMap { case (a, b) => List(a, b) }

  def midpoint(l: List[T]): Int = l.size / 2

  @annotation.tailrec def loop(current: List[T]): Boolean = {
    if (original == current) true
    else loop(shuffle(current.splitAt(midpoint(current))))
  }

  loop(shuffle(original.splitAt(midpoint(original))))
}

in_shuffle((1 to 52).toList)   // res0: Boolean = true

要求元素数为偶数。