38

tailrec optimizes functions where there is tail recursion. Why doesn't the compiler just optimize it anyway?

C compilers optimize for tail recursion. You don't have to mark the method as having tail recursion. The compiler just notices that the last operation is recursive. And that's that.

Why does this seemingly excessive keyword exist? Have I missed something? Is it purely for the convenience of the compiler, and not the user?

0

5 Answers 5

52

The keyword tells the compiler that the implementation of the function is required to be tail-recursive, and causes the compiler to report an error if the function is not actually tail-recursive. It protects the user from situations when a change to the implementation of the function causes it to no longer be tail-recursive, and causes an unexpected drop in performance (or a complete failure in production due to a stack overflow error).

3
  • 1
    If that is true, why cannot you have a method that is both open and tailrec?
    – PierreBdR
    Mar 6, 2020 at 7:47
  • 1
    I was also curious about this restriction and learned that it was originally supported, but later blocked due to compilation issues: youtrack.jetbrains.com/issue/KT-18541 @yole It seems like there should be a better solution than disabling the tailrec modifier on open members. It would be great if this restriction could eventually be lifted.
    – breandan
    May 26, 2021 at 1:22
  • @breandan It costs just one stack frame to call the recursive function from the method, but saves a lot stack frames.
    – ceving
    Nov 9, 2022 at 9:27
9

I'll go ahead and guess that this is to be able to more deliberately write tail-recursive functions. By requiring the keyword explicitly, you'll know that the compiler optimization will definitely happen (you won't be left guessing if the compiler optimized your function successfully or if you'll get a stack overflow at runtime), plus your code won't even compile if you break the rules of tail recursion for the function you've maked with tailrec, as the doc states:

To be eligible for the tailrec modifier, a function must call itself as the last operation it performs.

6
  • So does that mean that functions not marked with tailrec will never be optimized for tail recursion even if eligible? It certainly gives that impression (at least to me). Which gets me wondering if it's really just about giving compiler hints.
    – HelloWorld
    Aug 1, 2018 at 17:13
  • 3
    This is partly b/c the JVM itself cannot currently optimize for tail recursion (see softwareengineering.stackexchange.com/questions/272061/…). So many languages on top of the JVM, e.g. Clojure and Kotlin, expose a form (recur in Clojure) or a keyword (tailrec in Kotlin) to catch this at the language level.
    – tankthinks
    Aug 1, 2018 at 17:16
  • @HelloWorld, I know it's true for Clojure and it seems true for Kotlin based on the docs that the keyword tailrec is required for the Kotlin compiler to do the optimization.
    – tankthinks
    Aug 1, 2018 at 17:18
  • 1
    The compiler doesn't need hints to detect a tail-recursive function; it's quite a trivial check. I've explained why the keyword exists. What's the point in asking questions if you don't believe the answers you're given?
    – yole
    Aug 1, 2018 at 17:27
  • 2
    Counting the stack frames that Goetz mentions wouldn't be influenced by TCO. Those critical JDK methods could easily be excluded from the mechanism. Furthermore, it's doubly irrelevant to a complete separate language such as Kotlin. Kotlin has all the freedom in the world to apply TCO wherever it sees fit, but it makes the conscious choice of doing it only on explicit request. With a TCO'd method you lose important diagnostic information and it's great that you can choose where to apply it. Aug 1, 2018 at 18:01
3

Recall official Kotlin documentation just says that :

When a function is marked with the tailrec modifier and meets the required form, the compiler optimises out the recursion, leaving behind a fast and efficient loop based version instead

Which strongly suggests that this conversion to a loop is not warranted to take place if the tailrec keyword is not present.

1
const val MAX_VALUE = Int.MAX_VALUE

fun calculateFixedPointCosine(after: Int = 1) : Int {
    return if(after >= MAX_VALUE - 5) after
    else {
        calculateFixedPointCosine(after + 1)
    }
}

tailrec fun tailRecCalculateFixedPointCosine(after: Int = 1) : Int {
    return if(after >= MAX_VALUE - 5) after
    else tailRecCalculateFixedPointCosine(after + 1)
}

fun main(args: Array<String>) {
    val startWithoutTailRec = System.currentTimeMillis()
    val withoutTailRec = calculateFixedPointCosine(1)
    val endWithoutTailRec = System.currentTimeMillis()

    val startWithTailRec = System.currentTimeMillis()
    val withTailRec =  tailRecCalculateFixedPointCosine(1)
    val endWithTailRec = System.currentTimeMillis()

    println("Time Elapsed without tail rec: ${endWithoutTailRec - startWithoutTailRec}, value: $withoutTailRec")
    println("Time Elapsed with tail rec: ${endWithTailRec - startWithTailRec}, value: $withTailRec")
}

Now run this code and most probably you will encounter a StackOverflowException.

Now comment out the code for without tailrec method calls, and it will run successfully. Which implies that tailrec has modified your recursion.

Now as the question states that why the compiler is not optimizing it anyway? The compiler does optimization but that is not guaranteed. meaning that it will not happen always. If the compiler sees fit, it will optimize and some time it wouldn't.

In case you want to enforce this optimization, guaranteed, use tailrec keyword.

0

Code example based on @szmb13 @yole answers

try run this code with n=10000, if you got error try to add tailrec keyword and run it again

fun fibonacci(n: Int, a: BigInteger, b: BigInteger): BigInteger {
    return if (n == 0) b
    else fibonacci(n - 1, a + b, a)
}

You can see the different

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.