尾递归与 重构

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.)

两次调用方法总是运行两次.没有方法调用结果的自动记忆 - 这将是非常难以自动完成的.