尾递归与尾递归重构

Question

我有这个方法，

  private def getAddresses(data: List[Int], count: Int, len: Int): Tuple2[List[Address], List[Int]] = {
    if (count == len) {
      (List.empty, List.empty)
    } else {
      val byteAddress = data.takeWhile(_ != 0)
      val newData = data.dropWhile(_ != 0).tail
      val newCount = count + 1
      val newPosition = byteAddress.length + 1
      val destFlag = byteAddress.head
      if (destFlag == SMEAddressFlag) {
        (SMEAddress().fromBytes(byteAddress) :: getAddresses(newData, newCount, len)._1, newPosition :: getAddresses(newData, newCount, len)._2)
      } else {
        (DistributionList().fromBytes(byteAddress) :: getAddresses(newData, newCount, len)._1, newPosition :: getAddresses(newData, newCount, len)._2)
      }
    }
  }

我很想重写它，因此

  private def getAddresses(data: List[Int], count: Int, len: Int): Tuple2[List[Address], List[Int]] = {
    if (count == len) {
      (List.empty, List.empty)
    } else {
      val byteAddress = data.takeWhile(_ != 0)
      val newData = data.dropWhile(_ != 0).tail
      val newCount = count + 1
      val newPosition = byteAddress.length + 1
      val destFlag = byteAddress.head
      val nextIter = getAddresses(newData, newCount, len)
      if (destFlag == SMEAddressFlag) {
        (SMEAddress().fromBytes(byteAddress) :: nextIter._1, newPosition :: nextIter._2)
      } else {
        (DistributionList().fromBytes(byteAddress) :: nextIter._1, newPosition :: nextIter._2)
      }
    }
  }

我的问题是

1. 第一个方法是尾递归吗？
2. 它是如何运作的？我在最后一行调用该方法两次。它评估单独的方法调用什么吗？
3. 哪个版本更高效，或者我怎样才能更高效地编写它。

如果代码有异味，请原谅我，我是 scala 新手。

谢谢

Answer 1

这些都不是尾递归。仅当递归调用仅作为某个执行路径上的最后一项发生时才会发生这种情况。如果您可以通过跳转到代码开头来替换调用，不保存状态但重新标记输入变量，那么它就是尾递归。 （在内部，这正是编译器所做的。）

要将普通递归函数转换为尾递归函数，当可能时，您需要传递任何存储的数据，如下所示：

private def getAddresses(
  data: List[Int], count: Int, len: Int,    // You had this already
  addresses: List[Address] = Nil,           // Build this as we go, starting with nothing
  positions: List[Int] = Nil                // Same here
): (List[Address], List[Int]) {
  if (count==len) {
    (addresses.reverse, positions.reverse)  // Return what we've built, reverse to fix order
  }    
  else {
    val (addr,rest) = data.span(_ != 0)
    val newdata = rest.tail
    val position = addr.length + 1
    val flag = addr.head
    val address = (
      if (flag) SMEAddress().fromBytes(addr)
      else DistributionList().fromBytes(addr)
    )
    getAddresses(newdata, count+1, len, address :: addresses, position :: positions)
  }
}

尾递归版本比非尾递归版本更有效-尾递归版本，如果其他条件相同。 （在这种情况下，可能不是，因为列表必须在最后反转，但它有一个巨大的优势，如果您使用较大的 len，它不会溢出堆栈。

）一个方法两次总是运行两次。没有自动记忆方法调用的结果——这很难自动完成。

Answer 2

为了使其更加“Scala”，您可以在 getAddresses 内部定义尾递归函数，如下所示

def getAddresses(data: List[Int], len: Int) = {
  def inner(count: Int, addresses: List[Address] = Nil, positions: List[Int] = Nil): (List[Address], List[Int]) = {
    if (count == len) {
     (addresses.reverse, positions.reverse)
    } else {
      val (byteAddress, rest) = data.span(_ != 0)
      val newData = rest.tail
      val newPosition = byteAddress.length + 1
      val destFlag = byteAddress.head
      val newAddress = (if (destFlag == SMEAddressFlag) SMEAddress else DistributionList()).fromBytes(byteAddress)
      inner(count+1, newAddress :: addresses, newPosition :: positions)
    }
  }

  inner(0)   //Could have made count have a default too
}

Answer 3

由于所有输入都是不可变的，并且结果列表始终具有相同的长度，因此我想到了这个解决方案。

private def getAddresses(data:List[Int], count:Int, len:Int):Stream[(Address,Int)] = {
   if (count == len) {
      Stream.empty
   }else{
      val (byteAddress, _::newData) = data.span(_ != 0)
      val newAddress =
         if (byteAddress.head == SMEAddressFlag) SMEAddress().fromBytes(byteAddress)
         else DistributionList().fromBytes(byteAddress)

      (newAddress, byteAddress.length + 1) #:: getAddresses(newData, count+1, len)
}

1. 它不返回一对列表，而是返回一个对的列表。这使得递归一次变得很容易。如果您需要单独的列表，可以使用 map 来提取它们，但您也许可以重新构建程序的其他部分，以便更干净地处理成对的列表，而不是将 2 个列表作为参数一切都结束了。

2. 它不返回列表，而是返回延迟评估的流。这不是尾递归，但是延迟计算流的方式也可以防止堆栈溢出。如果您需要一个严格的列表，您可以对该函数的结果调用toList。

3. 演示了其他有用的技术，例如使用 span 与模式匹配来在单行代码中计算 byteAddress 和 newData 。如果有利于提高可读性，您可以添加回一些我删除的 val。

Answer 4

1. 否。如果给定执行路径中的最后一个调用是递归调用，则方法是尾递归的。这里评估的最后一个调用将是 ::，它不是递归调用，因此它不是尾递归。
2. 是的，如果你调用一个方法两次，它就会被评估两次。
3. 第二个更有效，因为在这里您只调用该方法一次。