Почему эта функция не является хвостовой рекурсивной? - PullRequest
Новая
       9

Почему эта функция не является хвостовой рекурсивной?

0 голосов
/ 28 февраля 2020

Я пишу простой метод для списка типа структуры. Я хочу, чтобы он был оптимизирован для хвостовой рекурсии, но не могу понять, почему компилятор жалуется.

Случай Cons является хвостовой рекурсией, но не повторяется, даже если они делают один и тот же вызов для одного и того же структура данных. Может быть, я неправильно понимаю хвостовую рекурсию. Если бы кто-то мог это прояснить, я был бы благодарен. 

  final def contains[B >: A](target: B): Boolean = this match{
    case Empty => false
    case Cons( h, t ) => h == target || t.contains( target )
    case Repeat( _, l ) => l.contains( target )
  }

1 Ответ

3 голосов
/ 28 февраля 2020

Хвосто-рекурсивная функция определяется как та, чей последний оператор либо возвращает простое значение, либо вызывает сам себя, и это должен быть единственный рекурсивный вызов.

Во-первых, ваша функция не имеет рекурсивной функции. звонки, потому что вы больше не вызываете contains function . Но вы вызываете метод contains другого экземпляра.
Эту проблему можно решить, переместив логи c за пределы класса.

Однако есть еще один общая проблема.
Это: h == target || t.contains( target ) не является хвостово-рекурсивным вызовом, поскольку последняя операция - это не вызов contains, а * или 1015 * (||) , выполненный с его результатом.

Вот как вы можете выполнить его рефакторинг. 

def contains[A](list: MyList[A])(target: A): Boolean = {
  @annotation.tailrec
  def loop(remaining: MyList[A]): Boolean = 
    remaining match {
      case Empty => false
      case Cons(h, t) => if (h == target) true else loop(remaining = t)
      case Repeat(_, l) => loop(remaining = l)
    }
  loop(remaining = list)
}

Если вам все еще нужен метод в вашем классе, вы можете переслать его для вызова этой вспомогательной функции, передав this в качестве начального значения.

...