N'est-ce pas le code dans la queue de l'récursive de style?

Question

Je suis un peu nouveau à la Scala de l'essayer lors de la lecture de Début de Scala par David Pollack. Il définit une simple fonction récursive qui charge toutes les chaînes de caractères dans le fichier:

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

Il est élégant et génial sauf qu'il avait jeté une StackOverflow exception lorsque j'ai essayé de charger un énorme fichier de dictionnaire.

Maintenant, comme je le comprends Scala prend en charge la queue de récursivité, de sorte que la fonction d'appel ne pouvait absolument pas de débordement de la pile, probablement compilateur de ne pas le reconnaître? Donc après quelques recherches sur google, j'ai essayé @tailrec annotation à l'aide du compilateur, mais il a dit

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

Suis-je la compréhension de la queue de la récursivité de mal? Comment puis-je corriger ce code?

Answer 1

Scala ne peut l'optimiser si le dernier appel est un appel à la méthode elle-même.

Eh bien, le dernier appel n'est pas d' allStrings, c'est en fait à l' :: (contre) méthode.

Un moyen de faire la queue récursive est d'ajouter un accumulateur de paramètre, par exemple:

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

Pour éviter l'accumulateur fuite dans l'API, vous pouvez définir la queue méthode récursive comme une méthode imbriquée:

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

Answer 2

Ce n'est pas la queue récursive (et ne pourra jamais être) parce que la dernière opération n'est pas un appel récursif de allStrings, c'est un appel à l' :: méthode.

La meilleure façon de résoudre ce est avec un imbriquée méthode qui utilise un accumulateur:

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

Dans ce cas particulier, vous pouvez également soulever l'accumulateur à un paramètre sur allStrings, de lui donner une valeur par défaut de Nil, et d'éviter la nécessité d'une méthode interne. Mais ce n'est pas toujours possible, et il ne peut pas être appelé bien à partir du code Java si vous êtes inquiet au sujet de l'interopérabilité.