Why is `tailrec` a modifier keyword applied at the function level?

Language Design
1

There are actually 2 parts to this question:

  1. tailrec, IMHO, stands out as an oddball in the modifier keyword group as it has no effect on semantics, instead operating in compiler-space optimization world. Why isn’t it e.g. an annotation?

  2. It seems to me that applying it at the function declaration level is restrictive. Consider the following:

tailrec fun f(x: Int): Int = when {
    x <= 10 -> x
    x % 2 == 1 -> f(x - 7) + 1
    else -> f(x + 1)
}

In this case I have no way to specify that I intend one branch to be tail recursive and the other not to be. A related issue is that I may actually intend for one such branch to be tail recursive but the function as a whole is tail recursive so long as some other branch makes a tail recursive call.

An approach that seems better all around (to me) would be an annotation at the expression level:

fun f(x: Int): Int = when {
    x <= 10 -> x
    x % 2 == 1 -> f(x - 7) + 1
    else -> @TailRec f(x + 1)
}

it just seems like the “right” place to put it. The compiler’s job is very straightforward as well, probably even simpler than its current responsibilities.

As a bonus [and from Kotlin: Tail recursion for mutually recursive functions - Stack Overflow I gather that the JVM doesn’t support mutual recursion (or “proper tail calls” in the general case) but if it were to be supported in the future] this approach could be easily extended:

fun f(x: Int): Int = if (x > 100) @TailCall g(x / 2) else x
fun g(x: Int): Int = @TailCall f(x + 4)
3 Likes
2

Hi,
It is a little bit late but I want to answer it anyway. The problem here is not kotlin. The problem here is the written code. It is always desireable to prefer an iterative process over a recursive one. So you have to transform it into an iterative one. So I did it!
From:

tailrec fun f(x: Int): Int = when {
    x <= 10 -> x
    x % 2 == 1 -> f(x - 7) + 1
    else -> f(x + 1)
}

into:

fun f (x: Int): Int = f(0, x)
tailrec fun f (sum:Int, x:Int) = when {
  x <= 10 -> sum+x
  x % 2 == 1 -> f(sum+1, x-7)
  else -> f(sum, x+1)
}

...
@Test
fun testF() {
  Assert.assertEquals(10, f(10))
  Assert.assertEquals(5, f(11))
  Assert.assertEquals(7, f(12))
  Assert.assertEquals(10, f(21))
}

But my question is (that’s the reason why I answered to this post); Do you plan to remove the keyword ‘tailrec’?
I mean, there are several languages in the past, they do it without the keyword. As I know even C++ optimizes these situations to an iteration, if you switch on the code optimization level O3. So I think kotlin should not need the keyword ‘tailrec’. The compiler should be able to recognize automatically these situations.

1 Like
3

tailrec is not for compiler, but for developer. Compiler translates tailrec function into a loop. Developer must be sure in that. Otherwise you might think that your function is tail-recursive, but it’s not and you’ll get unexpected stack overflow with some parameters. With tailrec compiler checks that all recursive calls are indeed tail calls and will either compiler that code into a loop or stop with error.

Think about tailrec as of override. Compiler, obviously, do not need that keyword, but developer does need it.

1 Like
4

That is not a valid argument. It is not the job of the language to prevent you to do these mistakes. BTW normally it is easy to see if a function has a recursive or an iterative process.
So is there an optimization if I leave that keyword ‘tailrec’? I thought, only if I put the keyword ‘tailrec’ then the compiler optimizes it? If it is so that the compiler is optimizing it, then the discussion is redundant.

5

Of course it is the job of the language to prevent you from mistakes. The point is not about recursive functions, but about tail-recursive functions which could be optimized automatically into a loop.

1 Like
6

Tail recursive functions

Kotlin supports a style of functional programming known as tail recursion. This allows some algorithms that would normally be written using loops to instead be written using a recursive function, but without the risk of stack overflow. 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:

val eps = 1E-10 // "good enough", could be 10^-15
tailrec fun findFixPoint(x: Double = 1.0): Double =
  if (Math.abs(x - Math.cos(x)) &lt; eps) x else findFixPoint(Math.cos(x))
7

So, maybe I did not understand something? But I could run this code without problems! It compiles!

tailrec fun f(x: Int): Int = when {
    x <= 10 -> x
    x % 2 == 1 -> f(x - 7) + 1
    else -> f(x + 1)
}

And?

8

Actually, Kotlin does not support automatic tail recursion optimization (neither does the JVM). Tail recursion for example breaks stack traces and debuggers. These are not major issues, but currently the view is that automatic tail recursion is not desirable (there was a discussion on this for Java a long time ago as well - see this blog post) on the JVM. So in this case the keyword does double duty, one to opt in to the optimization, the other to ensure it is valid.

1 Like
9

is not tail recursive as it needs a stack to remember the +1. It is valid code, but is not fully tail recursive. It is still possible to optimize the third case. Think of tail recursion as updating the parameter values and jumping back to the top of the function.

10 
tailrec fun f(x: Int): Int = when {
    x <= 10 -> x
    x % 2 == 1 -> f(x - 7) + 1
    else -> f(x + 1)
}

The compiler will indeed optimize the last case. The compiler will also generate a warning about the second case.

11

And that is not possible without the additional keyword?

12

Finding code to optimize with tailrec is possible without the keyword. As you said, languages like C++ do it.
If I remember the earlier discussion about it correctly, the reason for the keyword is following. It is easy to accidentally break tail-recursion when changing a function at a later point. The keyword is manly there, to let the programmer express that this function should be tailrecursive. It’s about being expressive. Also it allows for the warning I mentioned. If tailrecursion would be done automatically you could no longer display warnings about places where it’s not possible.

1 Like
13

Why is that so?

14

Recursion is limited due to stack overflow exceptions. There is only a limited amount of data that is reserved for stack variables (which include primitives you use in functions as well as return addresses for function calls, etc). Based on the architecture of the JVM (and also most other modern native architectures) there is only a fixed size for that. You have can set the stack size for the jvm when you start a program but that size is can’t be changed after that.
If you have a recursive function you will use up that space quite quickly. While modern programming languages support recursion you will at some point run into an issue where you run out of space on the stack and get an exception and crash.
By transforming a recursive function into a iterative process you reduce the amount of stack size you need (instead of adding 1 function stack per iteration you might only need to increment a counter).

fun recursiveSum(numbers: List<Int>): Int {
    return if(numbers.size == 1) numbers[0]
    else numbers[0] + numbers.subList(1)
}
fun iterativeSum(numbers: List<Int>): Int {
    var sum = 0;
    for (number in numbers) {
         sum += number;
    }
    return sum;
}

The iterative version will need to push 1 stack entry for each number in the list while the iterative version only needs a single stack entry.
You could fix that issue with a bigger stack size but depending on the size of the list you can always run out of space that way.
Storing data in the heap (place where object instances are stored) is much better, because the heap is only limited by how much RAM you have in your computer.

All that said recursion is nothing bad. You just have to be aware that there are limits on how deep your recursion can go before you run out of memory. tailrec is there to help with that. It allows you to mark a recursive function for the compiler to optimize into an iterative algorithm. That way you get an easy to read algorithm (recursion is often easier to understand) without the problems of it.

15

You’d get a warning on this:

Recursive call is not a tail call

16

Yes. There are some limitations on tail-recursion. The kotlin compiler warns you when it is not possible to use.
https://kotlinlang.org/docs/reference/functions.html#tail-recursive-functions

To be eligible for the tailrec modifier, a function must call itself as the last operation it performs. You cannot use tail recursion when there is more code after the recursive call, and you cannot use it within try/catch/finally blocks.

The issue here is the + 1 at the end. Still the compiler will optimize the other 2 conditions of the function. This can still be useful if you know that the part that can’t be optimized is a rare case, that way you still get some recursion but not enough to cause an issue.

1 Like