两个函数之间的尾递归

Question

我想初始调用initConnection,它调用getData,它以递归方式调用自身,直到需要刷新connection-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中得到一个'不在尾部位置的递归调用'错误,仅用于initConnection函数.是不是可以在两个函数之间使用尾递归？或者它只与我的未来[回应]有关？

我也尝试删除未来[回应]

@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只保证优化Direct Tail-Recursion.这是因为至少有一些Scala打算运行的平台(特别是JVM)对高级控制流的支持有限.GOTO例如,JVM只支持一个intra-method ,这意味着为了实现比Direct Tail-Recursion更强大的功能,你会遇到Clojure的设计者Rich Hickey所解释的问题:互操作性,性能,高级控制流程 - 选择两个.Scala的设计师选择了Interop和Performance over Proper Tail Calls,Mutual Tail-Decursion,Tail-Decursion Modulo Cons,或类似的更强大的保证.

[注意:你不能在JVM上实现Proper Tail-Calls的经常重复的口头禅是不正确的.JVM上有很多Scheme实现,否则就会证明这一点.什么是真正的是,JVM规范本身并不能保证正确的尾调用.但是有一些方法可以实现它们,即:不要使用JVM的调用堆栈,实现自己的.但是,这可能会使您在Performance或Java Interop中花费很多,可能两者都有.Scala的TailCall库是如何在JVM上实现Proper Tail-Calls的另一个例子:Trampolines.

在您的第一个版本中initConnection,递归调用不是Tail-Call,因为评估的最后一个调用是对调用response.onFailure.

在你的第二个版本initConnection,没有递归调用所有,而尾部调用是getData.

Tail-Calls本质上等同于GOTO和Tail-Recursion本质上等同于一个while循环(在JVM上使用它实现GOTO).但是,JVM GOTO只能在单个方法中使用.因此,如果Scala想要实现Proper Tail-Recursion,他们要么必须实现自己的堆栈而不使用JVM,要将所有相互递归的方法组合成一个单一的巨型方法,这样才能GOTO工作,将异常用作蹦床或类似地做讨厌的东西,所有这些都会破坏Java Interop,Performance或两者兼而有之.

由于JVM是Scala设计人员的重要平台,而性能和平台Interop是重要的目标,他们选择放弃一个有用的语言功能,而不是放弃一个强大的平台.在规范中强制要求正确的尾部递归会使Scala在2015年之前的JVM或ECMAScript等平台上实际上无法实现.(或者更确切地说,它将禁止高性能,高度可互操作的实现.)