CODEWITHSUNDEEP
scalarecursiontail-recursion
kliew
kliew

Reputation: 3183

Tail recursion between two functions

I want make an initial call to initConnection which calls getData which calls itself recursively until it needs to refresh the connection-id, upon which it calls 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)
      }
  }

I get a 'Recursive call not in tail position' error in IntelliJ, only for the initConnection function. Is it not possible to use tail recursion between two functions? Or is it only related to my Future[Response]?

I also tried removing the 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)
  }

and get an error about initConnectioncontaining no recursive calls. Yet this is clearly infinitely recursive

Upvotes: 2

Views: 944

Answers (1)

Jörg W Mittag
Jörg W Mittag

Reputation: 369430

Recursion is when a method calls itself. Direct Recursion is when a method directly calls itself. A Tail-Call is the last call that is evaluated in a method. Tail-Recursion is a recursive call that is also a Tail-Call. Direct Tail-Recursion is a directly recursive call that is also a Tail-Call.

Scala only guarantees to optimize Direct Tail-Recursion. That is because at least some of the platforms that Scala intends to run on (particularly the JVM) only have limited support for advanced control flow. The JVM only supports an intra-method GOTO, for example, which means that in order to implement anything more powerful than Direct Tail-Recursion, you run into the problem which Rich Hickey, the designer of Clojure, paraphrased as: Interoperability, Performance, Advanced Control Flow – Pick Two. And the designers of Scala picked Interop and Performance over Proper Tail Calls, Mutual Tail-Recursion, Tail-Recursion Modulo Cons, or similarly more powerful guarantees.

[Note: the oft-repeated mantra that you cannot implement Proper Tail-Calls on the JVM is not true. There are plenty of Scheme implementations on the JVM that prove otherwise. What is true is that the JVM spec itself does not guarantee Proper Tail-Calls. But there are ways of implementing them, namely: don't use the JVM's call stack, implement your own. This, however, will cost you dearly in either Performance or Java Interop, probably both. Scala's TailCall library is another example of how to implement Proper Tail-Calls on the JVM: Trampolines.]

In your first version of initConnection, the recursive call is not a Tail-Call, because the last call that is evaluated is the call to response.onFailure.

In your second version of initConnection, there is no recursive call at all, and the Tail-Call is to getData.

Tail-Calls are essentially equivalent to GOTO and Tail-Recursion is essentially equivalent to a while loop (which on the JVM is implemented using GOTO). However, the JVM's GOTO only works within a single method. So, if Scala wanted to implement Proper Tail-Recursion, they would either have to implement their own stack and not use the JVM's, combine all the mutually recursive methods into one single giant method, so that GOTO works, use exceptions as trampolines or do similarly nasty stuff, all of which would break either Java Interop, Performance, or both.

And since the JVM is an important platform for the Scala designers, and Performance and platform Interop are important goals, they elected to rather give up a useful language feature than to give up a powerful platform. Mandating Proper Tail-Recursion in the spec would make Scala practically un-implementable on platforms such as the JVM or ECMAScript pre-2015. (Or rather, it would prohibit a high-performance, highly interoperable implementation.)

Upvotes: 8

Related Questions