时间戳

首页 > 解决方案 > 如何确定问题是否可以在 Scala 中使用尾递归解决

scala - 如何确定问题是否可以在 Scala 中使用尾递归解决

问题描述

如何确定是否可以通过尾递归解决问题陈述。是否有任何可以识别的问题特征？

标签： scalarecursionfunctional-programmingtail-recursion

解决方案

尾递归可以表达循环，所以任何可以用循环解决的问题，也可以用尾递归解决：

@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循环的语言是图灵完备的，因此尾递归至少可以用于计算自然数上的每个图灵可计算函数。

推荐阅读