Разве этот код не рекурсивный в стиле хвоста?

Я немного новичок в Scala, пробовал его, читая Beggining Scala Дэвидом Поллаком. Он определяет простую рекурсивную функцию, которая загружает все строки из файла:

def allStrings(expr: => String): List[String] = expr match {
    case null => Nil
    case w => w :: allStrings(expr)
}

Это изящный и удивительный, за исключением того, что он исключил исключение StackOverflow, когда я попытался загрузить огромный файл словаря.

Теперь, насколько я понимаю, Scala поддерживает хвостовую рекурсию, так что вызов функции не может переполнять стек, возможно, компилятор его не распознает? Поэтому после некоторого googling я попробовал аннотацию @tailrec, чтобы помочь компилятору, но он сказал

error: could not optimize @tailrec annotated method: it contains a recursive call not in tail position
def allStrings(expr: => String): List[String] =

Я понимаю неправильную рекурсию хвоста? Как исправить этот код?

Ответ 1

Scala может только оптимизировать это, если последний вызов является вызовом самого метода.

Ну, последний вызов не соответствует allStrings, это на самом деле метод :: (cons).

Способ сделать этот хвост рекурсивным - добавить параметр аккумулятора, например:

def allStrings(expr: => String, acc: List[String] = Nil): List[String] =
  expr match {
    case null => acc
    case w => allStrings(expr, w :: acc)
  }

Чтобы предотвратить утечку аккумулятора в API, вы можете определить хвостовой рекурсивный метод как вложенный метод:

def allStrings(expr: => String) = {
  def iter(expr: => String, acc: List[String]): List[String] =
    expr match {
      case null => acc
      case w => iter(expr, w :: acc)
    }
  iter(expr, Nil)
}

Ответ 2

Он не хвост рекурсивный (и никогда не может быть), потому что конечная операция не является рекурсивным вызовом allStrings, это вызов метода ::.

Самый безопасный способ разрешить это с помощью вложенного метода, который использует накопитель:

def allStrings(expr: => String) = {
  @tailrec
  def inner(expr: => String, acc: List[String]): List[String] = expr match {
    case null => acc
    case w => inner(expr, w :: acc)
  }
  inner(expr, Nil)
}

В этом конкретном случае вы также можете поднять аккумулятор на параметр allStrings, присвоить ему значение по умолчанию Nil и избежать необходимости использования внутреннего метода. Но это не всегда возможно, и его нельзя назвать красиво из Java-кода, если вас беспокоит взаимодействие.