两个函数之间的尾递归

Question

我想对 initConnection 进行初始调用，它调用 getData 递归调用自身，直到需要刷新连接 ID，然后调用 initConnection。

@tailrec private def initConnection(): Unit =
  {
    val response: Future[Response] = initHeaders(WS.url(url)).post(auth)
    response.onSuccess {
      case resp => getData(20, resp.asInstanceOf[Response].header("connectionID").get)
    }
    response.onFailure {
      case resp => initConnection()
    }
  }

@tailrec private def getData(requestsLeft: Int, sessionId: String): Unit =
  {
    if (requestsLeft == 0)
      {
        initConnection()
      }
    else
      {
        //send request and process data
        getData(requestsLeft - 1, sessionId)
      }
  }

我在 IntelliJ 中遇到 'Recursive call not in tail position' 错误，仅针对 initConnection 函数。两个函数之间不能使用尾递归吗？还是只和我的Future[Response]有关？

我也试过删除 Future[Response]

@tailrec private def initConnection(): Unit =
  {
    val response: Response = initHeaders(WS.url(url)).post(auth).value.get.get
    getData(20, response.header("ConnectionID").get)
  }

并收到有关 initConnection 不包含递归调用的错误。然而这显然是无限递归的

Answer 1

递归是方法调用自身。直接递归是指方法直接调用自身。 Tail-Call 是在方法中评估的最后一次调用。 Tail-Recursion 是一种递归调用，也是一种 Tail-Call。 Direct Tail-Recursion 是直接递归调用也是Tail-Call。

Scala 只保证优化直接尾递归。这是因为至少 Scala 打算运行的某些平台（尤其是 JVM）对高级控制流的支持有限。例如，JVM 只支持一个内部方法 GOTO，这意味着为了实现比 Direct Tail-Recursion 更强大的东西，你运行进入了 Clojure 的设计者 Rich Hickey 的问题，释义为：互操作性、性能、高级控制流——选两个。 Scala 的设计者选择了互操作性和性能，而不是适当的尾调用、相互尾递归、尾递归模数缺点或类似的更强大的保证。

[注意：你不能在 JVM 上实现正确的尾调用的经常重复的咒语是不正确的。 JVM 上有大量 Scheme 实现证明并非如此。是真实的是JVM规范本身不保证正确的尾调用。但是有种实现方式，即：不要使用 JVM 的调用栈，实现你自己的。然而，这将使您在性能或 Java 互操作方面付出高昂的代价，可能两者兼而有之。 Scala 的 TailCall 库是另一个如何在 JVM 上实现适当的尾调用的示例：Trampolines。]

在 initConnection 的第一个版本中，递归调用不是尾调用，因为计算的最后一个调用是对 response.onFailure.

的调用

在您的第二个版本 initConnection 中，根本没有递归调用，Tail-Call 是 getData.

Tail-Calls 本质上等同于 GOTO，而 Tail-Recursion 本质上等同于 while 循环（在 JVM 上使用 GOTO 实现）。但是，JVM 的 GOTO 只能在内一个方法中工作。因此，如果 Scala 想要实现适当的尾递归，他们要么必须实现自己的堆栈而不使用 JVM，将所有相互递归的方法组合成一个巨大的方法，以便 GOTO 有效，使用异常作为蹦床或做类似讨厌的事情，所有这些都会破坏 Java 互操作性、性能或两者。

并且由于 JVM 是 Scala 设计人员的重要平台，性能和平台互操作性是重要目标，因此他们宁愿放弃有用的语言功能也不愿放弃强大的平台。在规范中强制使用适当的尾递归将使 Scala 在 2015 年之前的 JVM 或 ECMAScript 等平台上几乎无法实现。（或者更确切地说，它将禁止高性能、高度互操作的实现。）

两个函数之间的尾递归

Tail recursion between two functions

scala

recursion

tail-recursion