Why are inline tailrec functions not allowed?

1

A use-case for an inline tailrec function is when you define a generic “sorted merge” algorithm over your datastructure with a custom fold function. tailrec allows to write the algorithm more cleanly, and inline is useful if the custom fold function wants an early return (i.e., if it’s a comparator).

Why is it prohibited? Looks like the compiler can first transform the function into a non-recursive form, and then inline it just like any other function.

Here’s some stupid code just for the sake of an example (doesn’t compile):

tailrec inline fun foo(n: Int, res: Int, mult: (Int, Int) -> Int): Int {
  if (n == 1) return res
  else return foo(n - 1, mult(n, res), mult)
}
4 Likes
2

I believe this could be an improvement to the compiler. Still inline is not really necessary in a function that can last.

3

It’s not about speed, it’s about non-local return.

4

My instict wants to say “how could it be possible to inline a tail recursive function”, because a true recursive function would not be possible to inline. But as mentioned that is not what happens when the code is compiled, so I am also a bit curious why this is not possible.

@baltiyskiy can you ellaborate what you mean with the non-local return?

5

@mantono Tail recursive function, marked with tailrec, is compiled into a loop. I don’t see anything that could prevent it from inlining.

As for non-local return, please refer to Kotlin docs: https://kotlinlang.org/docs/reference/inline-functions.html#non-local-returns

6

I went on to create a feature request for that: https://youtrack.jetbrains.net/issue/KT-27897