Разве это не код в хвостовой рекурсивной манере? - PullRequest
Новая
       49

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

45 голосов
/ 15 мая 2011

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

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] =

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

Ответы [ 2 ]

63 голосов
/ 15 мая 2011

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)
}
23 голосов
/ 15 мая 2011

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

...