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

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

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

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

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

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

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


scala functional-programming tail-recursion
person Grozz    schedule 14.05.2011    source источник

Ответы (2)


arrow_upward
66
arrow_downward

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

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

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

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)
}
person Ben James    schedule 14.05.2011
comment
Копируя мой ответ, вы забыли аннотацию @tailrec. Это не только простой способ заставить компилятор подтвердить ваши ожидания, но и полезный совет для последующих сопровождающих. - person Kevin Wright; 15.05.2011
comment
Кевин, я не копировал ваш ответ, я фактически вносил правки, когда вы писали. Но вы хорошо отметили аннотацию, за которую я проголосовал за ваш ответ, несмотря на ваше ехидное замечание :) - person Ben James; 15.05.2011
comment
Я собирался удалить свой, когда увидел, что мы ответили одновременно, но не сделал этого, заметив, что вы использовали параметр по умолчанию вместо вложенного метода. Вы можете оценить, насколько сомнительно это выглядит, когда при последующем редактировании этот вариант будет добавлен в ваш ответ. - person Kevin Wright; 15.05.2011

arrow_upward
24
arrow_downward

Это не хвостовая рекурсия (и никогда не может быть), потому что последняя операция - это не рекурсивный вызов 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, если вас беспокоит взаимодействие.

person Kevin Wright    schedule 14.05.2011