Как определить, можно ли решить проблему с помощью Tail-рекурсии или нет в Scala - PullRequest
Новая
       45

Как определить, можно ли решить проблему с помощью Tail-рекурсии или нет в Scala

0 голосов
/ 04 февраля 2019

Как определить, можно ли решить проблему с помощью хвостовой рекурсии или нет.Есть ли какие-то характеристики проблемы, по которым можно это идентифицировать?

1 Ответ

0 голосов
/ 04 февраля 2019

Хвостовая рекурсия может выражать циклы, поэтому любая проблема, которая может быть решена циклом, также может быть решена с помощью хвостовой рекурсии: 

@scala.annotation.tailrec
def myWhile(condition: => Boolean)(body: => Unit): Unit = 
  if (condition) { body; myWhile(condition)(body) }

var i = 0

myWhile { i < 10 } { i += 1; println(i) }
// 1
// 2
// 3
// 4
// 5
// 6
// 7
// 8
// 9
// 10

В частности, выражение итерация очень естественно с хвостовой рекурсией: 

def processElement[A, B](el: A)(restOfTheElements: Traversable[A]): B = {
  doSomethingWithEl
  val (nextElement, newRest) = doSomethingToGetNextElement(restOfTheElements)
  processElement(nextElement)(newRest)
}

Циклы событий (например, GUI, веб-сервер, ядро ​​операционной системы) естественно хвостовой рекурсии: 

def processEvent[A](event: A)(eventPump: EventPump[A]): Unit = {
  doSomethingWithEvent
  processEvent(eventPump.nextEvent)(eventPump)
}

Также,язык, который содержит только циклы WHILE, является полным по Тьюрингу, поэтому хвостовая рекурсия может по крайней мере использоваться для вычисления каждой вычисляемой по Тьюрингу функции по натуральным числам.

...