Хвостовая рекурсия против. Рефакторинг

Ни один из них не является хвостовой рекурсией. Это происходит только тогда, когда рекурсивные вызовы возникают только как самый последний элемент на некотором пути выполнения. Если бы вы могли заменить вызов переходом к началу кода, не сохраняя состояния, но переименовывая входные переменные, то это хвостовая рекурсия. (Внутренне это именно то, что делает компилятор.)

Чтобы преобразовать обычную рекурсивную функцию в хвостовую рекурсивную функцию, когда это возможно, вам необходимо передать вперед любые сохраненные данные, например:

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

Вызов метода дважды всегда запускает его дважды. Нет автоматического запоминания результатов вызовов методов — это было бы крайне сложно сделать автоматически.

Просто чтобы сделать его более «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
}

Поскольку все ваши входные данные неизменяемы, а ваши результирующие списки всегда будут иметь одинаковую длину, вместо этого я подумал об этом решении.

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, которые я удалил, если полезно иметь их имена для удобочитаемости.

1. Нет. Метод является хвостовой рекурсией, если последний вызов в данном пути выполнения является рекурсивным вызовом. Последним оцененным здесь вызовом будет ::, который не является рекурсивным вызовом, поэтому он не является хвостовым рекурсивным.
2. Да, если вы вызовете метод дважды, он будет оценен дважды.
3. Второй более эффективен, так как здесь вы вызываете метод только один раз.