如何识别是否有问题可与尾递归在斯卡拉解决或不

Question

如何才能辨别是否有问题语句还可以用尾递归或没有得到解决。有没有通过一个可识别的问题的任何特点？

Answer 1

尾递归可以表达循环，这样就可以通过循环来解决任何问题，也可以通过尾递归来解决：

@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，web服务器，操作系统内核）是自然尾递归：

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

此外，只包含WHILE环路语言是图灵完备，所以尾递归至少可以用来计算每一个图灵可计算函数在自然数。